Searching - notes-archive/DSA GitHub Wiki

Binary Search

Pre req: Array should be sorted

I/p: arr[] = [10,20,30,40,50,60]
     x = 20
o/p: 1

I/p: arr[] = [5,15,25]
     x = 25
o/p: 2

I/p: arr[] = [10,20,30,40,50,60]
     x = 35
o/p: -1

I/p: arr[] = [5,5]
     x = 5
o/p: 0 or 1

Naive solution:

Linear Search

Compare x with each and every element and return the index of the element if x is found in the array

• Array need not to be sorted if this approach is followed
• Tc: O(n), Sc: O(1)

int linearSearch(a,n,x){
  for(int i = 0; i < n; i++){
    if(a[i]==x) return i;
    else return -1;
  }
}

Binary Search (Iterative)

TC: O(logn), Auxillary Space : O(1)

int binarySearch(a,n,x){
  int low = 0, high = n-1;
  int mid = Math.floor((low + high) / 2);

  while(low <= high){
      if(a[mid] == x) return mid;
      else if (a[mid] > x){
         high = mid -1;
      }
      else low = mid+1;
  }
  return -1;
}

Binary Search (Recursive)

TC: O(logn), SC: O(logn) -> for call stack

int binarySearch(a,n,x,low,high){
  //base case
  if(low > high) return -1;

  int mid = Math.floor((low + high)/2);

  if(a[mid]==x) return mid;
  else if(a[mid] > x) return binarySearch(a,n,x,low,mid-1);
  else return binarySearch(a,n,x,mid+1,high);
}

tree-representation:

[10,20,30,40,50,60,70], x = 25

bSearch(a,7,25,0,6)  // returns -1
|__mid = (0+6)/2 = 3
|__a[mid] > x
   |__ bSearch(a,7,25,0,2)  // returns -1 to parent
       |__mid = (0+2)/2 = 1
       |__ a[mid] < x
           |__bSearch(a,7,25,2,2) // returns -1 to parent
               |__ mid = (2+2)/2 = 1
               |__ a[mid] > x
                   |__ bSearch(a,7,25,2,1) // returns -1 to parent

Analysis of Binary Search