标准模板, 给定nums, 找target并返回下标, 找不到返回-1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int binarySearch(int[] nums, int target) {
  int left = 0, right = nums.length;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      return mid;
    }
    return -1;
  }
}

变种1: 在nums中, 找比target小的数字中index最大的, 没有比target小的则返回-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int binarySearch(int[] nums, int target) {
  int left = 0, right = nums.length, ans = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      // Current mid could be a potential answer
      ans = mid;
      // Look right to see if there is a better answer
      left = mid + 1;
    } else if (nums[mid] >= target) {
      right = mid - 1;
    }
    return ans;
  }
}

变种2: 在nums中, 找比target小的数字中index最小的, 没有比target小的则返回-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int binarySearch(int[] nums, int target) {
  int left = 0, right = nums.length, ans = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] <= target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      // Current mid could be a potential answer
      ans = mid;
      // Look left to see if there is a better answer
      right = mid - 1;
    }
    return ans;
  }
}

变种3: 在nums中, 找target, 但是如果出现多个target, 返回index最小的那个(first bad version), 如果没有target, 返回-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int binarySearch(int[] nums, int target) {
  int left = 0, right = nums.length, ans = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      // Current mid could be a potential answer
      ans = mid;
      // Look left to see if there is a better answer
      right = mid - 1;
    }
    return ans;
  }
}

变种4: 在nums中, 找target, 但是如果出现多个target, 返回index最大的那个, 如果没有target, 返回-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int binarySearch(int[] nums, int target) {
  int left = 0, right = nums.length, ans = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      // Current mid could be a potential answer
      ans = mid;
      // Look left to see if there is a better answer
      left = mid + 1;
    }
    return ans;
  }
}

总结一下就是标准的binary search是不用引入一个ans变量, 直接找就完事儿. 但是如果出现找某个数字previous smaller或者next larget这种. 我们引入一个ans变量, 时时更新它. 最后ans存的就是我们要的结果. 这个思路记牢, 模板也就记牢了.