Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。
一、题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104
二、思路分析：
分析题意，一个排序数组和一个目标值 满足二分查找,同时要求了必须使用时间复杂度为 O(log n) 的算法，也指明了需要使用二分查找的方法
二分查找法的基本思想：将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的数x作比较，如果a[n/2]为需要的数字x则找到，算法终止；如 果x< a[n/2]，则我们只要在左半部继续搜索；如果x>a[n/2]，则我们只要在右 半部分继续搜索。
left = 0, right = nums.length - 1
循环的条件是：left <= right，
中间位置： mid = left + ((right -left)/1)
按照二分法进行循环，找出结果
三、AC 代码：
class Solution {
public int searchInsert(int[] nums, int target) {
int left =0 ;
int right = nums.length -1;
int mid = 0;
while(left <= right){
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 -1;//不存在返回-1
}
}四、总结：
确定要查找的区间到底是左闭右开[left, right)，还是左闭又闭[left, right]，这就是不变量。
然后在二分查找的循环中，坚持循环不变量的原则，很多细节问题，自然会知道如何处理了。
希望通过这此刷题理解二分法的做法。
