2. Binary Search #

Created Wednesday 11 December 2019

• Works only if array is sorted.
• Time O(N)

Implementation:

• Things we had problems with, odd and even. Doesn’t matter, numbers are geometric.

// arr - input array
// n - size of array
// val - element to be searched
int BinarySearch(int arr[], int n, int val){
  int l = 0, r = n - 1, mid = (l + r) / 2;

  while(arr[mid] != val && l < r)
  {
    mid = (l+r)/2;
    if(arr[mid]<val)
      l = mid+1;
    else
      r = mid-1;
  }

  if(arr[mid]==val)
    return mid;
  return -1;
}