二分探索

gistfile1.md

vはleft以上、right未満の範囲に存在する

va[left] <= v < va[right]

function contaions(int v, int[] va) {
  if (va.length == 0) {
    return false;
  }
  int left = 0, int right = va.length;
  
  while (left + 1 < right) {
    int m = left + (right - left) / 2;
    int x = va[m];
    if (v >= x) {
      // va[m] <= v < va[right]
      left = m;
    } else {
      // va[left] <= v < v[m]
      right = m;
    }
  }
  return va[left] == v;
}