题目描述

35. 搜索插入位置

解题思路

• 题型数组、二分查找变式—寻找第1个大于等于目标值的元素

• 关键二分查找的关键点就是—两边夹高数上又叫作夹逼准则。left和right确定答案所在区间通过mid(把区间划分为[left,mid]&[mid+1,right]两个区间)来缩小区间范围直到left==right,即获得答案。

  • 为什么呢存在如下定理A <= target <= B当A = B时target = A = B

• 思路
  1.确定答案可能取值区间[left,right]
  2.left = 0;right = array.length;(因为此题中array.length也有可能为答案
  3.while(left<right)不考虑所谓的什么闭区间就仅仅代表它本身的含义当left==right时即找到答案跳出循环

  • 为什么呢因为很多问题就这么设计一定要等到最后才能确定问题的答案在很多时候不能在循环体中找到答案。

  4.确定循环体中分支的两种情况

  • a.target>array[mid]left=mid+1
  • b.else (即target<=array[mid])right=mid

  5.left==right跳出循环体后return right
  🌟为什么呢直接return left/right呢我们来分析一下跳出循环后的两种情况

  • 情况1最简单的一种情况即夹逼准则成立时找到答案array[left]=array[right]=targer这个很好理解。此时array[left]==targert
  • 情况2即没找到与target相等的元素的下标。因为array[left]<=target<=array[right]是默认恒成立的–即target应该存在于这个区间。即left指针指向[left,right]第一个小于等于target的元素right指针指向[left,right]最后一个大于等于target的元素。在[left,right]实际区间范围不断缩小的过程中当left和right重合时right指向的是[0,array.length-1]这个区间第一个大于等于target的元素.我个人目前觉得在理解层面上return right比return left要好理解一些虽然两者达到的效果是一样的

代码实现–Java

class Solution {
    public int searchInsert(int[] nums, int target) {
         int left=0,right=nums.length;//因为nums.length可能为答案
         while (left<right){
            int mid=left+(right-left)/2;//防止溢出但其实left和right表示数组小标没什么必要
            if(target>nums[mid]){
                left=mid+1;//下一次搜索区间为[mid+1,right]
            }
            else{
                right=mid;//下一次搜素区间为[left,mid]
            }
        }
        return right;
    }
}

总结&易错

• 【易错】二分查找的重点就划分区间、逐渐缩小、两边夹关于划分区间这题我用的划分为[left,mid]和[mid+1,right]为什么不是[left,mid-1]和[mid,right]呢—因为会出现死循环

//下面是把区间划分为[left,mid-1]和[mid,right]的情况错误代码
class Solution {
    public int searchInsert(int[] nums, int target) {
         int left=0,right=nums.length;//因为nums.length可能为答案
         while (left<right){
            int mid=left+(right-left)/2;//防止溢出但其实left和right表示数组小标没什么必要
            if(target<nums[mid]){
                right=mid-1;//下一次搜索区间为[left,mid-1]
            }
            else{
                left=mid;//下一次搜素区间为[mid,right]
            }
        }
        return right;
    }
}

死循环分析
输入[1,3,5,6] 2出现超时。分析
第一次循环mid=2;区间被分为[0,1],[2…4]下一次搜索区间为[0,1],left:0,right:1
第二次循环mid=0left:0,right:1下次循环区间还是[0,1]
第三次循环mid=0left:0,right:1,下次循环区间还是[0,1]
…死循环

• 解决方法把(left+right)/2修改为(left+right+1)/2

  • 其实本质死循环的原因是只有两个元素时mid指针指向的是前一个元素再mid=left+right)/2不能把区间[left,mid-1]和[mid,right]其缩小所以才会发生死循环。通过修改为mid=(left+right+1)/2此时可以缩小区间即不会发生死循环。

• 【重点】二分法的关键是缩小区间死循环发生的原因是某次循环没有缩小区间导致二分失败。

• 【重点】此题right设置为array.length的原因是array.length也有可能是问题答案

• 【重点】将二分查找的判断条件写成while(left<right)代表的是搜索区间为[left,right]一旦left==right,即此时找到问题答案立即跳出循环。

• 【重点】循环不变量在[left,right]搜索答案

👩‍🎨write in the end:

• 🙇‍♀️建立此专栏的初衷是为了监督自己每天认真刷一个题积少成多。并把自己每次刷题的思路、收获以博文的形式分享出来帮助更多人以及方便后续复习。如果有兴趣的同学可以订阅此专栏我们一起刷题一起交流进步和学习专栏LeetCode每日一题–进击大厂