[leetCode]二分查找例题与反证法证明（35. 搜索插入位置）

[leetCode]二分查找例题与反证法证明（35. 搜索插入位置）

目录

一、题目简介

代码：

一、题目简介

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

请必须使用时间复杂度为 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

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码：

其中最难理解的是返回值为什么是left或者right+1

只需要推出最终的right的停留位置一定是比target小的最大的数的位置即可

简略的反证法：假设right停止的位置的数等于target，则会在前面的代码中返回。

假设right停止的位置的数大于target，则此时left<=right，则mid<=right则循环不会停止，故于假设矛盾。

假设right停止的位置的数小于比target小的最大的数，则一定有一次循环中right的位置大于等于比target小的最大的数的位置，此时有nums[mid]>target才能移动right。但此时mid一定小于比target小的最大的数的位置，因此target>=nums[mid]，故与假设矛盾。

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:#二分查找n=len(nums)left=0right=n-1#当left<=right，始终符合target属于 [left,right] while(left<=right):mid=left+int((right-left)>>1)if(nums[mid]<target):left=mid+1elif(nums[mid]>target):right=mid-1else:return mid#如果没找到对应数，最后right会落在大小比target小的最大的数的位置#而left会落在right+1的位置上#因为最后一次判断时left=right#而此时nums[left]<target#或return left+1return left