Binary Search

Binary Search is used to search for an item from a sorted array. It is an example that uses the divide and conquer method. Binary Search is better than linear Search because it reduces the search area by half each time.

However, our array must be sorted. Otherwise, we cannot apply the binary search algorithm.

Pseudo Code

1. Calculate the midpoint of the current sub-array.

2. Stop if the item you want to search for is in the middle.

3. Otherwise, if the item is less than what’s in the middle, change the endpoint to just to the left of the middle.

4. Otherwise, if the item is greater than what’s in the middle, change the start point to just to the right of the middle.

5. Repeat until the sub-array is of size zero.

Worst Case

The worst-case scenario for the binary search algorithm is either when the target item is not present in the array at all or when the target item is found only at the very end.

Worst case time complexity = O(log(n))

Best Case

The best case occurs in a binary search algorithm when the target item is the middle element of the array.

Best-case time complexity Ω(1)

Disadvantages

It requires sequential storage.

This method is not suitable for a linked list.

A Binary Search Algorithm can be implemented in the following two ways,

1. Iterative Method

C++ code

2. Recursive Method

C++ code