Understanding Binary Search and Linear Search

Contents :

• Understanding Linear search and its time complexity
• Understanding Binary search
• Implementation of binary search in C++

---

1. Understanding Linear search and its time complexity :
   Given an array and a key element and we need to check if the given key is in the array. If it is present then at what position it is located ?
   Linear Search : is comparing key element with each and every element of the array. If it is matched with some element, then whoa! we get the index of key element in the array.
   Time Complexity :O(n) because we are comparing key with each and every element of the array.
   Implementation Hint: Run a for loop from 0 to N and compare array[i] with key. If array[i] = key, then save the position in some variable and break the loop.
   
2. Understanding Binary search :
   We can apply binary search only on sorted values. If we are given a sorted array of n elements and we need to search an element in the array then we can search it in only log(n) time using binary search.
   In each iteration of binary search, we find the middle element of array and compare it with key element and if key is lesser than middle element then it also means that it is lesser than all the elements to the right of middle of element, since the array is sorted. So we ignore rightmost part of the array and our array shrinks to half the size.
   Similarly we ignore the leftmost part of the array if key is greater than middle element of the array.
   We stop this process on 2 conditions :
   1. Found Condition : If the middle element is equal to the key element.
   2. Not Found Condition : If the array shrinks to size zero.
   Example :
   

   a[ 7 ]  =  1   3   5   6   22   102   111
   Key = 5
   left = 0
   right = n = 7
   Iter 1: mid = (left + right) / 2  = 3
    a[ 3 ] > key, So we now know that all elements
    with index >= 3 are greater than Key and so 
    range 3 to 7 of the array are useless, hence 
    we change variable right to 2.
   
   left = 0, right = 2
   
   Iter 2: mid = (0 + 2) / 2 = 1
    a[ 1 ] = 3 which is less than key, so we 
    change left variable to mid+1 i.e. left = 1+1 =2
     
   left = 2, right = 2
   
   Iter 3: mid = (2 + 2) / 2 = 2
    a[ 2 ] = key = 5 , 
    So key is present in array at index 2.
     
   

3. Implementation in C++ :

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

   #include <iostream> using namespace std; // Binary Search Function int search(int *a, int n, int key){ int left = 0; int right = n-1; while(left <= right){ int mid = (left + right) >> 1; if(a[mid] == key){ return mid; // Element found at index mid }else if(a[mid] < key){ left = mid + 1; }else{ right = mid - 1; } } return -1; // Element not found } int main() { int n; cin >> n; int a[n]; // Sorted Array for(int i = 0 ; i < n ; i ++){ cin >> a[i]; } int key; cin >> key; // Key element cout << search(a, n, key); return 0; }

   Complexity : Lets consider the size of array be 2¹⁰ = 1024. In each iteration we divide the array into 2 equal halves. So,
   

   Iteration Number  : Size of array
      1              : 1024 / 2 = 512
      2              : 512 / 2 = 256
      3              : 256 / 2 = 128
      4              : 128 / 2 = 64
      5              : 64 / 2 = 32
      6              : 32 / 2 = 16
      7              : 16 / 2 = 8
      8              : 8 / 2 = 4
      9              : 4 / 2 = 2
      10             : 2 / 2 = 1
   

   So from this we can see that we can search an element in a sorted array of size 1024 in just 10 iterations.
   Clearly 10 comes from log2(1024).
   Hence, time complexity of binary search is log2(n) where n is the size of the array.

So we can say that if the given list is sorted we must apply binary search if we need to search an element in the list. Otherwise we have one more choice Linear Search whose complexity is O(n) which is far worst than binary search.
Don't do this crazy thing on an unsorted list : Sort the list first and then apply binary search. Sorting a list takes O(nlog(n)) which is greater than O(n) linear search. In case of unsorted array linear search performs well.
Thank you buddies for reading this post !
The End !!