Binary Search or Half-Interval search

The Video is in Hindi Language

Binary search is a Divide & Conquer algorithm used to search for an element in an array.

It requires the array to be sorted.

If array is not sorted then the only way to search in the array is Linear search.

Binary search divide the number of elements to be searched in two halves in each iteration and only one half remains relevant to be searched and the other is ignored. Therefore, even if the element is not present in the array we don't need to traverse all the element in the list.

It keep three variables low, high and mid, each storing the index of first element, last element and middle element in the array being searched.  Initially value of low (L) will be 0 (position of first element of array), high(H) will be n-1 (position of last element in the array) and we are searching in the entire array, then the size reduces to half and we either search the first half or the second half depending on whether element at mid is greater than less then the element being searched.

Algorithm:

// position of first and last element
1. low = 0; high = n-1;
2. If low is greater than high          // entire array is searched
      RETURN -1                         // NOT FOUND
3. mid = (low+high)/2
4. IF (element at mid == Searched value)
      Element FOUND. Return the index.
   ELSE
      IF (element at mid < Searched value)
           //Go to the step 2 for the part of the array, before mid.
           high = mid-1;
           GOTO step 2.
       ELSE            // element at mid > searched element
          //Go to the step 2 for the part of the array, After mid.
          low = mid+1;
          GOTO step 2.

Below pictures shows the working of algorithm:

Let the array be {6, 13, 14, 25, 33, 43, 51, 53, 64, 72, 84, 93, 95, 96, 96}, and let the data to be searched is 33.

1. Since arr[L] <= data <=arr[H].

2. Calculate mid, M = (L+H)/2

3. Since data<arr[M], and all elements on the right of M will be greater than arr[M], hence we can ignore the elements on the right of M and never need to search in arr[M] - arr[H].

Note: This is not there in linear search. We can never ignore anything in linear search. 4. L and H area adjusted according to the new bounds and M is calculated again.

5. Since arr[M] < data. the value cannot be present on the left side of M (including M).

6. Calculating M again, and then checking it against data.

7. updating L and H again.

8. Calculating M = (L+H)/2.

9. arr[M] == data. Hence return M (index where data is found).

Code:

/** Non-Recursive Function */
int bSearch(int * arr, int n, int data)
{
    int l=0, h=n-1, m;
    while(l <= h)
    {
        m = (l + h) / 2;
        if(arr[m] == data)
            return m;              // FOUND.
        else if(arr[m] < data)
            l = m + 1;
        else
            h = m – 1;
    }
    return -1;                    // NOT FOUND
}

Below is the recursive solution for Binary search

/** Recursive Function */
int bSearch(int * arr, int l , int h, int data)
{
    if(l > h || arr[l] > data || arr[h] < data)
        return -1;             // NOT FOUND.
    else
    {
        int m = (l+h)/2;
        if(arr[m] == data)
            return m;         // FOUND.
        else if (arr[m]<data)
            return bSearch(arr, m+1, h, data)
        else
            return bSearch(arr, l, m-1, data);
    }
}

Time Complexity:

Best Case: O( 1 ) Found at the middle of entire Array Worst Case: O( lg (n) ) Not found Average Case: O( lg (n) )

Space Complexity:

Non-Recursive: O(1) Recursive: O( lg(n) )

Variations:

---

1. Write code to find the position of pivot in a sorted array rotated around a pivot. Solution:

Step-1. Find position of pivot in the array using Binary Search. The condition for checking arr[mid] == data will be changed to see that it should be the last element in the first sub array.
    if( (mid

---

2. A Sorted array is rotated around the pivot, write b-search algorithm to search in that array. Solution:

Step-1. Find position of pivot in the array using Binary Search as shown in the first variation.
Step-2: Once the position of pivot is found, perform binary search in the left sub array and right sub array independently.

---

3. Given an Array of numbers and a number x. Write function to search for two elements in the array, whose sum is x. Solution: See this post.