Click here to download u01/searches.cc.

/* SI 335 Unit 1
 * searches.cc
 * Contains C++ implementations of the three algorithms for the Sorted
 * Array Search problem.
 * 
 * All three algorithms return the index of x, if it is found, or else
 * -1 to indicate NOT_FOUND.
 */

#include <algorithm>
using std::min;

int linearSearch (const int A[], int n, int x) {
  int i = 0;
  while (i < n && A[i] < x) 
    ++i;
  if (i < n && A[i] == x) return i;
  else return -1;
}

int binarySearch (const int A[], int n, int x) {
  int left = 0;
  int right = n-1;
  while (left < right) {
    int middle = (left + right) / 2;
    if (x <= A[middle])
      right = middle;
    else
      left = middle + 1;
  }
  if (A[left] == x) return left;
  else return -1;
}

int gallopSearch (const int A[], int n, int x) {
  int i = 1;
  while (i < n && A[i] <= x)
    i *= 2;
  int left = i/2;
  int right = min(i,n) - 1;
  int ret = binarySearch (A+left, right-left+1, x);
  if (ret >= 0) return ret + left;
  else return -1;
}