Binary search

Binary Search is a searching algorithm for searching an element in a sorted list or array. it is more efficient than linear search as its complexity is Ο(log n). This search algorithm works on the principle of divide and conquer.

Algorithm: half of elements are ignored after each comparision

let X be the element to be searched 

• Compare X with the middle element of the array.
• If X is same as middle element return the mid index.
• Else If X is greater than the mid element, then X will lie in right half of mid element. So we now search X in only the right half and left half is ignored
• Else if X is smaller, search for X in the left half ignore the right half.

Middle element can be found by using any of the two formulas:

1) mid= (low+ high) /2 

Or

2) mid=low+(high-low) /2

how binary search works?

 it is mandatory for the target array to be sorted,we need to search the location of value 23 using binary search.

                                                       

First, we shall determine mid of the array by using this formula :

mid = low + (high - low) / 2

Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

now we should compare the mid with the element to be searched as  16<23 we should search in the right half now and ignore the left half

again when we calculate the mid using above formula we get mid as 7 , as the element to be searched is smaller than the mid ,56>23 so we now search in the left half of the mid.

now left is 5 + (6- 5 ) / 2 = 5(integer value of 5.5) so mid is 5, now the element to be searched is equal to mid so return mid

the element to be searched is in 5th index

Iterative Function:

n is the no. of elements in array 

and is element to be searched

int binarySearch(int arr[],int n,int x) 
{ 
    int l=0; int r=n-1;
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if we reach here, then element was 
    // not present 
    return -1; 
}

Recursive Function:

int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 

int main()
{   
  int n; cin>>n;
  int x; cin>>x;
  int arr[n];
  
  for(int i=0;i<n;i++)
  cin>>arr[i];

  cout<<binarySearch(a,0,n-1,x);
}

Time Complexity: O(Log N)