益阳市网站建设_网站建设公司_MySQL_seo优化

一、题目

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

二、思路

1、二分查找中，我们要维护一个搜索范围，闭区间写法：left=0,right=n-1，表示初始搜索范围是整个数组。

2、初始化是left = 0, right = n - 1（数组索引），搜索区间是[0,n-1]，两端都有效。

3、循环条件：while(left <= right)，当left == right时，说明只剩一个元素，仍然需要检查它是否等于 target。如果是left < right就会漏检查这个情况。

4、中间值：int mid = left + (right - left) / 2; //

5、防溢出写法

6、最后返回left，当循环结束时，left恰好指向第一个大于等于target的元素位置，正是我们要插入的位置。

总结：闭区间写法的核心思想是：始终维护一个有效的搜索区间[left, right]，每次缩小范围，直到区间为空，此时left恰好是答案。

三、代码

class Solution { public int searchInsert(int[] nums, int target) { int len = nums.length; int left = 0, right = len - 1; while(left <= right){ int mid = left + (right - left) /2; if(target == nums[mid]){ return mid; }else if(target > nums[mid]){ left = mid+1; }else{ right = mid-1; } } return left; } }