Circular Binary Search

13 Oct 2011 | By Mihai Roman | Tags google search algorithms C/C++ divide and conquer
You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum number in this list. Find any given number in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, i.e.: 38, 40, 55, 89, 6, 13, 20, 23, 36.

This is a programming puzzle that makes use of classic binary search. As I’ve already said in my opening post , binary search is a helper function that you should be able to write really fast during the live coding on phone screening.

int binsearch(int* v, int x, int p, int q) {
  if (p <= q) {
    int mid = (p + q) / 2;
    if (x < v[mid]) return binsearch(v, x, p, mid - 1);
    if (x > v[mid]) return binsearch(v, x, mid + 1, q);
    return mid;
  }
  return -1;
}

// Search x in subsequence v_p, … v_q
// Call with p = 0, q = n - 1
int search(int* v, int x, int p, int q) {
  if (p <= q) {
    int mid = (p + q) / 2;
    if (v[mid] == x) return mid;
   
    if (v[mid] < v[q] && x > v[mid] && x <= v[q]) return binsearch(v, x, mid + 1, q);
    if (v[mid] > v[p] && x < v[mid] && x >= v[p]) return binsearch(v, x, p, mid - 1);
    
    if (v[mid] <= v[q]) return search(v, x, p, mid - 1);
    return search(v, x, mid + 1, q);
  }
  return -1;
}

blog comments powered by Disqus