JIYIK CN >

Binary search is the most popular and efficient search algorithm. In fact, it is the fastest search algorithm. Like jump sort, it also requires the array to be sorted. It is based on a divide and conquer approach where we divide the array into two halves and then compare the item we are searching for with the item in the middle. If the middle item matches, we return the index of the middle element; otherwise, we move to the left or right half based on the value of the item.

Binary Search Algorithm

Suppose we have an unsorted array A[]containing nelements and we want to find an element X.

• Let lo be 0 and hi be n - 1.
• I'm sorry.
  • 设 mid=lo + (hi - lo)/2。
  • If A[mid] == X return mid.
  • If A[mid] < X, then lo = mid+1.
  • else if A[mid] > X then hi= mid-1。
• If the element is not found, -1 is returned.

Binary Search Example

1. Let lo be 0 and hi be 8.
2. Calculate mid to be 4. Since A[mid]<X, set lo=4+1=5.
3. Calculate mid to be 6. Since A[mid]<X, set lo=6+1=7.
4. Calculate mid to be 7. Since A[mid]=8, 7 is returned.

Suppose we have an array , (1,2,3,4,5,6,7,8,9)and we want to find X - 8.

Implementation of Binary Search Algorithm

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x)
{
    while (lo <= hi) {
        int m = lo + (hi - lo) / 2;
        if (arr[m] == x)
            return m;
        if (arr[m] < x)
            lo = m + 1;
        else
            hi = m - 1;
    }
    return -1;
}

int main(void)
{
    int n = 9;
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x = 8;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1) {
        cout << "Element not found !!";
    }
    else cout << "Element found at index " << result;
    return 0;
}

Complexity of Binary Search Algorithm

Time Complexity

• Average situation

When we do a binary search, we search half and discard the other half, reducing the size of the array by half each time.

The expression for time complexity is given by recursion.

T(n) = T(n/2) + k , k is a constant.

The result of this recursion gives logna time complexity of O(logn). It is faster than both linear search and jump search.

• Best Case

The best case is when the middle element is the one we are searching for and it is returned in the first iteration. The time complexity for the best case is O(1).

• Worst case scenario

The worst case time complexity is the same as the average case time complexity. The worst case time complexity is O(logn).

Space complexity

In case of iterative execution, the space complexity of this algorithm is O(1)since it does not require any data structures except temporary variables.

In case of a recursive implementation, the space complexity is 1/2 due to the space required for the recursive call stack O(logn).