Binary Search

If we have an array that is sorted, we can use a much more efficient algorithm called a Binary Search. In binary search each time we divide array into two equal half and compare middle element with search element.

Searching Logic

• If middle element is equal to search element then we got that element and return that index

• If middle element is less than search element we look right part of array

• If middle element is greater than search element we look left part of array.

The complexity of Binary Search Technique

• Time Complexity: O(1) for the best case. O(log2 n) for average or worst case.

• Space Complexity: O(1)

Binary Search - Algorithm

Binary Search - Example

Search for 6 in given array

Example:

#include<iostream>
using namespace std;

int binarySearch(int a[], int start, int end, int key) {
   if(start <= end) {
      int mid = (start + (end - start) /2); //mid location of the list
      if(a[mid] == key)
         return mid;
      if(a[mid] > key)
         return binarySearch(a, start, mid-1, key);
         return binarySearch(a, mid+1, end, key);
   }
   return -1;
}

int main() {
   int n, skey, loc;
   cout << "Enter number of items: ";
   cin >> n;

   int arr[n]; 
   cout << "Enter items: " << endl;

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

   cout << "Enter which element to search in the list: ";
   cin >> skey;

   if((loc = binarySearch(arr, 0, n, skey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

Output

Enter number of items: 10
Enter items:
-1 5 6 18 19 25 46 78 102 114
Enter which element to search in the list: 6
Item found at location: 2