标准二分查找
使用场景
- 排序的数组（排序，且支持随机读取）
- 不大不小的数据， 大了的话，数组太大，木有那么大的连续空间，小了话，基本没有优势。
- 因为二分查找能够减少比较次数，所以如果比较操作比较复杂的话，那么不管数组大小都优先二分查找。
public static int binarySearchStandard(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while (end >= start) {
int mid = start + ((end - start) >> 1);
if (nums[mid] < target) {
start = mid + 1;
} else if (nums[mid] > target) {
end = mid - 1;
} else {
return mid;
}
}
return -1;
}
代码注意事项：
- 循环条件 end >= start
- mid = start + ((end - start) >> 1) 防止 采用 （end + start) / 2可能的越界行为。
- start = mid + 1； end = mid - 1；防止死循环。
变体：
- 找出有序数组里，第一个等于target的元素下标
- 找出有序数组里，最后一个等于target的元素下标
public static int binarySearchFirstOne(int[] array, int target) {
int start = 0;
int end = array.length - 1;
while (end >= start) {
int mid = start + ((end - start) >> 1);
if (array[mid] == target) {
if (mid == 0 || array[mid - 1] != target) return mid;
end = mid - 1;
} else if (array[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
public static int binarySerarchLastOne(int[] array, int target) {
int start = 0;
int end = array.length - 1;
while (end >= start) {
int mid = start + ((end - start) >> 1);
if (array[mid] == target) {
if (mid == (array.length - 1) || array[mid + 1] != target) return mid;
start = mid + 1;
} else if (array[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
变体
- 找出有序数组里，第一个大于target的元素下标
- 找出有序数组里，最后一个小于target的元素下标
public static int binarySearchFirstGreaterOne(int[] array, int target) {
int start = 0;
int end = array.length - 1;
while (end >= start) {
int mid = start + ((end - start) >> 1);
if (array[mid] > target) {
if (mid == 0 || array[mid - 1] <= target) return mid;
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
public static int binarySearchLastLessOne(int[] array,int target) {
int start = 0;
int end = array.length - 1;
while (end >= start) {
int mid = start + ((end - start) >> 1);
if (array[mid] < target) {
if (mid == (array.length - 1) || array[mid + 1] >= target) return mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
上述的写法，很容易理解，不用想各种的边界条件，简直就是棒棒哒，核心就是对每次可能的候选值进行判断，而不是一窝蜂跳出循环之后在判断。
