文章目录

  • 题目
  • 思路
  • 代码呈现

题目

链接: link

思路

这题较简单，就是找到目标元素的下标，或者插入位置，如果不熟练的话，一开始想到的肯定是冒泡排序，就是一个一个查下去，然后返回下表，这种冒泡排序的时间复杂度为O(n)，相比较标准的二分查找来说大的很多，如果是标准的二分查找，时间复杂度就是O( l o g2xlog_{2}xlog2​x)是比较小的

但是在写代码的时候我们可以考虑新建一个元素来记录下标，比如下面的代码

int searchInsert(int* nums, int numsSize, int target) {int left = 0, right = numsSize - 1;int ans = numsSize;while (left <= right) {int mid = (left + right) / 2;if (target <= nums[mid]) {right = mid - 1;ans = mid;} elseleft = mid + 1;}return ans;}

这个代码的好处是比较清楚，一直用ans来几率下表，比所有数都大的时候就输出最开始赋值的numsSize

但是跳出这道题我们针对二分查找可以有个简单的认识
首先，设置

int left = 0, right = numsSize - 1;int mid = (left + right) / 2;

这种设置是很规范的，然后再看看你最后返回的是什么，比如说上面用按时输出ans，它是在 target <= nums[mid] 的条件下的，所以直接输出来就行了。

但是加入不让额外设置一个元素呢，那我们就学要用乐翻天来输出了

加入是以left的索引输出，那这样的话，就必须存在

if (target 》= nums[mid]) {right = mid - 1;}else left = mid + 1;

它的意思也很简单，就是因为要输出left，所以不能 (target >= nums[mid])的时候，不能变换left，否则永远无法使left指到下标，而是left-1可以指到

根据if的判断条件，left左边的值一直保持小于target，right右边的值一直保持大于等于target，而且left最终一定等于right+1，这么一来，循环结束后，在left和right之间画一条竖线，恰好可以把数组分为两部分：left左边的部分和right右边的部分，而且left左边的部分全部小于target，并以right结尾；right右边的部分全部大于等于target，并以left为首。所以最终答案一定在left的位置。

代码呈现

//用left返回int searchInsert(int* nums, int numsSize, int target) {int left = 0, right = numsSize - 1;while (left <= right) {int mid = (left + right) / 2;if (target > nums[mid]) {left = mid + 1;} elseright = mid - 1;}return left;}