Binary Search in Data Structures

Binary Search: An Overview

For anyone looking to get the most out of their data searching and analysis, binary search is an indispensable algorithm. Even if you're unfamiliar with computer science terminology, you can still benefit from knowing what binary search can do for your searches. This article explores binary search, describing its workings, Binary search in data structures examples, Algorithm for binary search, and providing advice for effective application in many industries. Join us for an introduction to binary search, whether you want to improve your searching abilities or are just curious about this quick sorting technique!

What is binary search?

Binary search is a powerful algorithm that is widely used in computer science and information technology. This search technique involves dividing a large dataset into smaller subsets until the desired item is found. Binary search is essential for quick searches, such as those conducted in databases or search engines, as it effectively locates items in sorted arrays with minimal comparisons. For programmers and software engineers, mastering this fundamental concept in computer science is crucial.

Types of binary search

Binary search is a search algorithm that works on sorted arrays or lists, dividing the search interval in half at every step. There are mainly three types of binary search:

1. Standard Binary Search: The standard binary search is the basic form of binary search. It searches for a specific element in a sorted array by repeatedly dividing the search interval in half.
2. Lower Bound Binary Search: The lower bound binary search finds the first occurrence of a given element in a sorted array. If the element is not found in the array, it returns the index of the smallest element that is greater than the given element.
3. Upper Bound Binary Search: The upper bound binary search finds the last occurrence of a given element in a sorted array. If the element is not found in the array, it returns the index of the smallest element that is greater than the given element

Binary Search Working

1. Start by defining the search interval: the entire array or list in the beginning.
2. Calculate the midpoint of the search interval.
3. Compare the value at the midpoint with the target value. If they match, the search is complete and the index of the value is returned.
4. If the midpoint value is greater than the target value, then the target value must be in the left half of the search interval. Set the search interval to be the left half of the original interval and go to step 2.
5. If the midpoint value is less than the target value, then the target value must be in the right half of the search interval. Set the search interval to be the right half of the original interval and go to step 2.
6. If the search interval is empty and the target value has not been found, then the target value is not in the array or list.

Steps of Binary Search Algorithm

Binary search is a searching algorithm that is used to search for a specific element in a sorted list or array. It works by repeatedly dividing the search interval in half until the target element is found or the interval becomes empty. Here are the steps of the binary search algorithm:

• Initialize the low and high pointers to the first and last elements of the sorted list or array, respectively.
• Calculate the mid-point of the interval as (low+high)/2.
• Compare the target element with the middle element of the interval.
• If the target element is equal to the middle element, then the search is successful and the index of the middle element is returned.
• If the target element is less than the middle element, then the search is repeated on the left half of the interval (i.e., low to mid-1).
• If the target element is greater than the middle element, then the search is repeated on the right half of the interval (i.e., mid+1 to high).
• Repeat steps 2-6 until either the target element is found or the interval becomes empty (i.e., low>high).
• If the target element is not found after the last iteration, then return a value indicating that the search was unsuccessful.

Binary search iterative algorithm

Iterative Binary Search Algorithm is a search algorithm used to find the position of a target value within a sorted array. The algorithm works by repeatedly dividing the sorted array in half until the target value is found or the search space is exhausted. The iterative implementation of the binary search algorithm involves using a loop to keep dividing the search space in half until the target value is found or the search space is empty. The steps involved in the iterative binary search algorithm are as follows:

1. Set the left and right indices of the search space to the first and last indices of the array, respectively. While the left index is less than or equal to the right index, do the following:
• Compute the middle index of the search space as the average of the left and right indices.
• If the target value is found at the middle index, return the index.
• If the target value is less than the value at the middle index, set the right index to be the index immediately to the left of the middle index.
• If the target value is greater than the value at the middle index, set the left index to be the index immediately to the right of the middle index.
• If the target value is not found in the array, return -1.
2. The iterative binary search algorithm has a time complexity of O(log n) where n is the size of the array. This makes it a very efficient search algorithm.

Example

 
 # Binary Search in python
 def binarySearch(array, x, low, high):
 # Repeat until the pointers low and high meet each other
 while low <= high:
 mid = low + (high - low)//2
 if array[mid] == x:
 return mid
 elif array[mid] < x:
 low = mid + 1
 else:
 high = mid - 1
 return -1
 array = [3, 4, 5, 6, 7, 8, 9]
 x = 4
 result = binarySearch(array, x, 0, len(array)-1)
 if result != -1:
 print("Element is present at index " + str(result))
 else:
 print("Not found")
 

Explanation

This example uses a binary search to find the index of a given element 'x' in a sorted array. If 'x' is found in the array, it prints the index; else, it prints "Not found."

Output

Element is present at index 1

Recursive binary search algorithm

Recursive Binary Search Algorithm is a searching algorithm used to find a specific element in a sorted array. This algorithm follows the Divide and Conquer strategy, where the problem is divided into smaller sub-problems until the desired result is obtained.

The algorithm works as follows:

• Take the middle element of the array.
• Compare the middle element with the target element. If the target element is equal to the middle element, return the index of the middle element.
• If the target element is greater than the middle element, ignore the left half of the array, and repeat the process from step 1 to step 2 with the right half of the array.
• If the target element is less than the middle element, ignore the right half of the array, and repeat the process from step 1 to step 2 with the left half of the array.
• If the target element is not present in the array, return -1 or a similar value to indicate that the element is not found.
• This algorithm is called "recursive" because it calls itself repeatedly until the desired result is obtained. It has a time complexity of O(log n) because it divides the problem into halves at each step, reducing the number of elements to search in half each time

Example

 
# Binary Search in python
 def binarySearch(array, x, low, high):
 if high >= low:
 mid = low + (high - low)//2
 # If found at mid, then return it
 if array[mid] == x:
 return mid
 # Search the left half
 elif array[mid] > x:
 return binarySearch(array, x, low, mid-1)
 # Search the right half
 else:
 return binarySearch(array, x, mid + 1, high)
 else:
 return -1
 array = [32, 44, 75, 86, 17, 80, 4]
 x = 44
 result = binarySearch(array, x, 0, len(array)-1)
 if result != -1:
 print("Element is present at index " + str(result))
 else:
 print("Not found")
 

Explanation

In this example, a recursive binary search technique is used to find the index of a given element 'x' in a sorted array. If 'x' is found, the index is printed; else, "Not found."

Output

Element is present at index 1

Advantages of Binary Search Tree in Data Structure

• Time Complexity: Binary search has a time complexity of O(log n), which is much faster than linear search (O(n)). This means that binary search is more efficient when dealing with large arrays or lists.
• Space Complexity: Binary search has a space complexity of O(1) because it only needs a few variables to store the low, high, and mid values. This makes it more memory-efficient compared to other algorithms.
• Easy to Implement: Binary search is a straightforward algorithm to implement, with only a few lines of code needed to execute it. This simplicity makes it a popular choice for beginners learning about algorithms and data structures.
• Versatility: Binary search can be used in a variety of applications, such as searching for a value in a sorted array, finding the minimum or maximum element in a rotated sorted array, or determining if an element exists in a matrix.
• Reliable: Binary search is a reliable algorithm because it always returns the correct result if the array or list is sorted. It eliminates the need to iterate over the entire array or list, which reduces the likelihood of errors in the implementation.

Disadvantages of Binary Search Tree in Data Structure

• Requires a sorted array: Binary search requires that the array be sorted before the algorithm is applied. If the array is not sorted, then the algorithm cannot be used.
• No dynamic updates: If the array is being updated dynamically, i.e., new elements are added or old elements are deleted, then the binary search cannot be used as it requires the array to be static.
• Limited applicability: Binary search is only applicable to arrays or lists that support random access. It cannot be applied to linked lists, for example, as they do not allow for constant time access to arbitrary elements.
• Space complexity: Although the binary search has a time complexity of O(log n), it has a space complexity of O(1). This means that it requires a constant amount of memory to run, but it cannot scale well for very large datasets.
• Performance issues in cache: Binary search may have performance issues when dealing with large datasets that do not fit into the cache memory of the computer. This is because the algorithm needs to access different parts of the array in a random manner, which can lead to cache misses and slow down the search.

Applications of Binary Search

• For more complicated machine learning algorithms, such as those for training neural networks or determining a model's ideal hyperparameters, binary search can be utilized as a building block.
• It can be used to look for computer graphics-related terms like ray tracing or texture mapping algorithms.
• It can be applied to database searches.

Binary Search Complexity Analysis

Best Case Complexity 

The best-case scenario for a binary search is when the element to seek is discovered in the first comparison, or when the first middle element is the element to search. Binary search has a best-case time complexity of O(1).

Average Case Complexity

Binary search has an O(logn) case time complexity on average.

Worst Case Complexity

The worst-case scenario in binary search is when we have to keep narrowing the search space until there is just one element. Binary search has a worst-case time complexity of O(logn).

FAQs

1. What is binary search in data structure?

A sorted collection can be effectively searched for a specific element using the binary search technique, which divides the search space in half frequently.

2. Why do we use binary search in data structure?

In sorted collections, binary search is used because it locates elements more quickly and requires fewer comparisons than linear search.

3. What are the different types of binary search in DSA?

Standard Binary Search, Lower Bound Binary Search, Upper Bound Binary Search, and Binary Search Trees are different varieties of binary search in DSA.

4. What is the main advantage of binary search?

With a temporal complexity of O(log n), binary search's main benefit is speed, which makes it perfect for big datasets.

5. What are the limitations of binary search?

Binary search is less effective for small datasets or when frequent insertions or deletions are required. It also requires a sorted collection and might not locate every case of a duplicate piece.

Summary

In conclusion, Binary Search is a powerful algorithm that can help you find an item in a list quickly and accurately. It's an invaluable resource for any developer who needs to search for something in a given data structure. The efficiency and simplicity of Binary Search make it a top option for software development. It is a trustworthy and effective search technique that works with any data structure. To increase the effectiveness of your program, go into Binary Search!

Take our free skill tests to evaluate your skill!

In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.

GET TEST NOW