Binary Search
Binary Search Overview
Related Questions
- Binary Search
- Search Insert Position
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Search a 2D Matrix
- Search a 2D Matrix II
- Find Peak Element
- 第一次做的时候没发现array本身是没有排序的。。
- 具体证明
- First Bad Version
- Find First and Last Position of Element in Sorted Array
- Kth Smallest Element in a Sorted Matrix
- Median of Two Sorted Arrays
- 这种排了序的序列要求log(n)时间复杂度的话，基本就是binary search
- 对于index +1 -1 的问题要关注一下
- Time Based Key-Value Store
- Longest Increasing Subsequence
- 可以通过binary search 优化dp过程
- dp数组的存放size为i的subsequence的最后一个值
- Wood Cut
- 排列组合一下都能知道哪啥当target。。。
Code
Binary Search
- 其中 int mid = left + (right - left) / 2 不直接使用 (left + right) / 2 因为若left + right 大于int的上限会出错，不过也可以用位操作替代 (left + right) >> 1;
- 此外这样取了之后中间点偏左
1 public int search(int[] nums, int target) {
2 int N = nums.length;
3 int left = 0, right = N - 1;
4 while (left <= right){
5 int mid = left + (right - left) / 2;
6 if (nums[mid] < target){
7 left = mid + 1;
8 }else if (nums[mid] > target){
9 right = mid - 1;
10 }else{
11 return mid;
12 }
13 }
14 return -1;
15 }
16
17// OR
18
19 while (left + 1 < right){
20 int mid = left + (right - left) / 2;
21 if (nums[mid] > nums[left]){
22 left = mid;
23 }else{
24 right = mid;
25 }
26 }
27 // check boundary