practice of programming

b.cc

// 一開始每個元素都是可能的答案 low和high分別指向頭尾有可能是答案的位置 
// (所以如果給定的長度是n, high是指向n-1的位置)

// 想想，如果mid不是我們要的答案，不論是low或high，指標都應該往前往後移一格
// 因為一開始說了，"low和high分別指向頭尾有可能是答案的位置"

// 最後想想如果low, high現在相鄰 下一個迭代只有兩種可能
// 1.找到 2.兩個指標現在指向同一個index
// 第二種情形的話，我們繼續往比較，這個最後一個還沒被查過的元素是不是我們要找的答案
// 2.找到 2.low超過high了

// [0, n) -> [0, n-1] or think of [low, high]
int binary_search(int *A, int n, int key){
  int low, high, mid;
  low = 0;
  high = n - 1;
  while(low <= high){
    mid = (low + high) / 2;
    if(A[mid]==key) return mid;
    else if(A[mid]<key) low = mid + 1;
    else high = mid - 1;
  }
  return -1; //not found
}