刷了几道二分查找相关的题，稍微总结一下。
二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
–wikipedia
无重复有序数组
即最基本的二分查找1
2
3
4
5
6
7
8
9
10int binarySearch (int[] nums, target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) retrun mid;
else if (target < nums[mid]) right = mid - 1;
else left = mid + 1；
}
return -1;
}
微扩展
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
设想循环走到了后期，即left和right分别指向两个相邻的数。这时会先判断left，如果target
总之跳出循环后，left指向总是target所在的位置，或是最近的大于target数(即插入位置)的位置，最后返回left即可(同理，right总是指向target或最近的小于target数)。
- 只需要最后返回值语句改为 return left;
有重复有序数组
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
第一版本：通过二分法找到一个与target相等的数组元素，然后向两边扩展，直到边界。
第二版本：
当程序运行到target=nums[mid]的情况时，它可能正处于一串重复的元素之中。这时候可能有两种情况：
- mid就是边界
- 边界在mid的左边
所以需要做的不是返回，而是继续对左边部分做二分查找，直到最后left与right重合，即为起始边界。或者如果目标值不在数组内，则left为最近的大于target数的位置。(e.g. num[] = {1}, target = 0;)
至于结束边界，可以反向思考。
看到一个复用代码的方式：找target+1的起始边界，target的结束边界为前者减一。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public int[] searchRange(int[] nums, int target) {
int start = getBound(nums, target);
//注意判断target不在数组中的情况
if (start == nums.length || nums[start] != target)
return new int[]{-1, -1};
return new int[]{start, getBound(nums, target+1)-1};
}
public int getBound(int[] nums, int target) {
int left = 0, right = nums.length-1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid])
if (left == right)//mid就是边界
break;
else //边界在mid左边
right = mid;
else if (target < nums[mid]) right = mid - 1;
else left = mid + 1;
}
return left;
}
特殊无序数组
有一种特殊的无序数组，是一组有序数组在某个点旋转。(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
无重复
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
第一版本：先通过二分查找找到分界pivot，然后判断target处于前半部分还是后半部分，最后对相应部分做二分查找。
第二版本：做正常二分查找，并在查找途中进行相应判断。得到mid后，判断left与mid位置值的大小。
- nums[left] <= nums[mid]，说明左半边是正常序列，即没有pivot。
- 判断target是否在左半边序列范围内，若在，则继续对左半边进行查找；(注意范围的定义)
- 若不在，则查找右半边。
- nums[left] > nums[mid]，pivot在左半边。原理与上面相同。
1 | public int search(int[] nums, int target) { |
有重复
Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?
Write a function to determine if a given target is in the array.
相比较于无重数组，多了一种特殊情况：e.g. 1111112 -> 1121111 -> 1111211
你无法判断pivot在左还是右，甚至是否存在。
这时nums[left] == nums[mid]就无法二分了，因为根本不知道往哪个区间二分，这时候只能遍历，直到left遇到一个其他数字，或超出范围。
最坏情况：全部都是同一个数的重复数组，O(n)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
else if (nums[left] < nums[mid]) {
if (target >= nums[left] && target < nums[mid])
right = mid-1;
else
left = mid+1;
}
else if (nums[left] > nums[mid]) {
if (target > nums[mid] && target <= nums[right])
left = mid+1;
else
right = mid-1;
}
else
left++;
}
return false;
}
总结
觉得最重要还是要理清最后left和right指向的到底是什么吧，总是想着想着就乱掉。
- 最后left和right指向两个相邻的数
- 先判断left，然后是right
- right指向的是小于等于target的数
- left指向的是大于等于target的数
发现有几道应用二分查找的无序数组的题，需要再探索一下。
Continue…