力扣初级算法（二分查找）

力扣初级算法(二分法)：

• 每日一算法：二分法查找

---

学习内容：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

2.二分查找流程：

left=0，right=nums.length,取mid为中间值

• 如果nums[mid]==target,返回mid值，循环终止
• 如果nums[mid]>target,就说明从mid到right之间的值都是“无用的”需要挪动right，而我们能知道的接近的一个无用的值是mid，因此right必须比mid还要小才行，也即是right=mid-1；
  同理，left=mid+1；
• 一直循环，除非找到mid值或者发现target根本不在目标中，也就是已经完全循环了一遍(left>right),这时候的left的值就是最接近target但又大于target的值（可以拿0来举例自己画一遍过程），因此return left

3.二分查找实现：

class Solution {public int searchInsert(int[] nums, int target) {//二分法//左边下标int left = 0;//右边下标int right = nums.length -1;while(left <= right){int mid = left + (right - left)/2;//相等，直接取出if(nums[mid] == target){return mid;}else if(nums[mid]<target){ //中间值小于所给的值，从中间值加一开始往右找left = mid + 1;}else if(nums[mid] > target){/中间值大于所给的值，从中间值减一开始往左找right = mid -1;}}return left;}
}

---

学习时间：

2023/08/03