经典的二分查找很好理解,也很好实现,那一起来看下二分查找的变形问题。
常见的二分查找变形问题有:
- 查找第一个等于待查找值的元素下标
- 查找最后一个等于待查找值的元素下标
- 查找第一个不小于给定值的元素下标
- 查找最后一个不大于给定值的元素下标
以第一个例子为例
假使给定数组 [1,2,4,5,7,7,9,9,11],待查找值为7,则返回结果应该是4
代码实现
package search;
/**
* @author TioSun
* 二分查找第一个等于待查找的元素下标
*/
public class BinarySearch1 {
public int search(int[] a, int n, int targetVal) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] > targetVal) {
high = mid - 1;
} else if (a[mid] < targetVal) {
low = mid + 1;
} else {
if (mid == 0 || a[mid - 1] != targetVal) {
return mid;
}
high = mid - 1;
}
}
return -1;
}
}
剩余三题的解题思路都和这个类似