Leetcode 解题模版 - Binary Search

适用场景

一种针对有序区间内的O(logN)的搜索方式，最常见用于已经排好序的Array

解题模版

public int binarySearch(int[] arr, int k) {
  int l = 0, r = arr.length - 1;
  while(l <= r) {
    //int mid = (l + r) / 2;   normally avoid since it might overflow for int
    int mid = l + (r - l) / 2;
    if(arr[mid] == k) {
      return mid; 
    } else if (arr[mid] > k) {
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return -1;  
}

三大模版：

1. 找一个准确值：

<1> 循环条件： l <= r

<2> 缩减搜索空间： 

         l = mid + 1

         r = mid - 1

2. 找一个模糊值（比4大的数字, first occurrence of 2）

<1> 循环条件：l < r

<2> 缩减搜索空间：

         l = mid 

         r = mid - 1

 or 

          l = mid + 1

          r = mid

3. 万用型

<1> 循环条件：l < r - 1

<2> 缩减搜索空间：

        l = mid 

        r = mid

变换场景

找一个模糊值

e.g. the first occurance of 2

public int binarySearch(int[] arr, int k) {
  int l = 0, r = arr.length - 1;
  while(l < r) {
    int mid = l + (r - l) / 2;
    if(arr[mid] < k) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return l;
}

e.g. last occurrence of 2

public int binarySearch(int[] arr, int k) {
  int l = 0, r = arr.length - 1;
  while(l < r) {
    int mid = l + (r - l + 1) / 2;
    if(arr[mid] > k) {
      r = mid - 1;
    } else {
      l = mid;
    }
  }
  return r;
}

万用型 （closest to 2）

<1> 循环条件：l < r - 1

<2> 缩减搜索空间：

l = mid

r = mid

public int binarySearch(int[] arr, int k) {
  int l = 0, r = arr.length - 1;
  while(l < r - 1) {
    int mid = l + (r - l) / 2;
    if(arr[mid] < k) 
      l = mid;
    else
      r = mid;
  }

  //upon determine the l/r, compare the value
  if(arr[r] < k) {
    return r;
  } else if(arr[l] > k) {
    return l;
  } else {
    return k - arr[l] > arr[r] - k ? r : l;
  }
}