二分法思想
在有序数列中，查找某个元素是否存在 扩展一下： 在有序数列中(通常是非递减，可以有重复元素)，查找第一个满足xx条件的元素 每次搜索区间减半，时间复杂度
O
(
l
o
g
n
)
O(logn)
O(logn)
模板1：有序数组中，查找是否存在某个元素，找到返回位置，找不到返回-1
public int binarySearch(int[] nums, int target) {
//初始左、右边界，覆盖完整位置
int left = 0;
int right = nums.length - 1;
int mid;
while (left <= right) {
mid = left + (right - left) / 2; // 避免int溢出
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
1.初始边界为0和n-1，如果你的下标从1开始，那就是1和n，效果一样，只需要确保初始闭区间一定能覆盖可能的位置 2.更新机制，匹配就返回mid，否则mid+1或mid-1。区间更新时不用带上mid，因为当前mid位置不匹配，所以mid不在下一轮查询的考虑范围之内。 3.深究一下： 条件为什么是left<=right？ 如果条件改成left 所以单纯找元素是否存在，条件是<= 模板2：有序数组中(非递减，可以有重复元素)，查找第一个满足xx条件(以>=5为例)的元素的位置。如果不存在，给出假设该元素存在的正确位置。 public int binarySearch(int[] nums) { int target = 5;//例子，找第一个>=5 int left = 0; int right = nums.length;//注意没有-1 int mid; while (left < right) { mid = left + (right - left) / 2; if (nums[mid] >= target) {//这里就是条件 right = mid; } else { left = mid + 1; } } return left; } 与模板1相比，有4个区别： 1.初始right，多一个 2.循环条件，是<不是<= 3.边界更新机制 4.返回值 1.初始right为什么不-1？ 因为要考虑所有可能得位置，如果target不存在，且比数组中所有元素都要大，那应该插入到最后一个位置，是n，不是n-1。 2、3、4举一个例子说明：1,2,3,5,6找4 初始left=0指向1，right=5指向6后面 mid=2, 3<4，left=3 mid=4, 6>4, right=4 mid=3, 5>4, right=3 left==right，退出循环 返回left=3 以上过程是正确的 如果循环条件是<=呢？ left=3, right=3 mid=3, 5>4, right=3 … 死循环了 再解释一下更新机制： 当nums[mid]>=target，因为我们要找第一个满足条件的，有可能在mid之前吧，所以要在left~mid搜索。但mid之前也有可能没啦，所以搜索区间不能把mid丢了。 因此更新方法为right=mid 当nums[mid] 咱们这个模板是闭区间实现的，也有开区间的版本，自行研究。 最后说明一下返回值， 返回left，其实并不保证nums[left]==target。若target不存在，left是假设存在，该插在的位置。 因此，如果需要确定有没有搜索到，还得判断一下返回值nums[left]==target 基于模板2，如果要找最后一个满足xx条件的呢？ 刚刚已经强调了，模板2处理的是找第一个满足xx条件的元素。 怎么找最后一个满足的呢？ 很简单，问题转化成：找第一个不满足xx条件的元素位置，找到的位置-1 推荐文章
发表评论