二分算法核心思路
二分查找的核心在于利用数据的二段性。在一个有序数组中，如果某个条件成立，其左侧（或右侧）必然满足某种规律，从而可以舍弃一半空间。相比暴力遍历的 O(N)，二分能将复杂度降至 O(log N)。
1. 标准二分查找
在有序数组中查找目标值 target，找到返回下标，否则返回 -1。
class Solution {
public int search(int[] nums, int target) {
// left 和 right 分别指向当前搜索区间的两端
int left = 0;
int right = nums.length - 1;
while (left <= right) {
// 防止整数溢出
int mid = left + (right - left) / 2;
if (target > nums[mid]) {
// 目标在右半部分 [mid+1, right]
left = mid + 1;
} else if (target < nums[mid]) {
// 目标在左半部分 [left, mid-1]
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
}
注意：循环条件是
left <= right，因为当left == right时区间内仍有一个元素需要检查。
2. 在排序数组中查找元素的第一个和最后一个位置
题目要求找到目标值的起始和结束下标。由于存在重复元素，不能直接套用标准二分，需要分别寻找左边界和右边界。
{
[] searchRange([] nums, target) {
[] ret = [];
ret[] = ret[] = -;
(nums.length == ) {
ret;
}
;
nums.length - ;
(left < right) {
left + (right - left) / ;
(nums[mid] < target) {
left = mid + ;
} {
right = mid;
}
}
(nums[left] != target) {
ret;
}
ret[] = left;
left = ;
right = nums.length - ;
(left < right) {
left + (right - left + ) / ;
(nums[mid] > target) {
right = mid - ;
} {
left = mid;
}
}
ret[] = right;
ret;
}
}
