目录

🍕题目一

🍔思路

🍟代码

🍕 题目二

🍔思路：

🍟代码

🍕题目三

🍔思路：

🍟代码：

🍕题目一

704. 二分查找

🍔思路

从中间开始查找，因为列表是有序的（而且是升序的），

目标值小于中间的数，就向左走（左边的数小）

目标值大于中间的数，就向右走（右边的数大）

🍟代码

classSolution:
defsearch(self, nums: List[int], target: int) ->int:
left=0right=len(nums)-1whileleft<=right:
mid= (left+right)//2iftarget==nums[mid]:
returnmideliftarget<nums[mid]:
right=mid-1else:
left=mid+1return-1l= [-1,0,3,5,9,12]
s=Solution()
print(s.search(l,5))

🍕 题目二

278. 第一个错误的版本

🍔思路：

先一个左指针，一个右指针，区间从【1到n】        注意这个细节，决定返回什么

（1）while(l<=r): 判断左指针是否小于右指针（就是mid值是否有效）

（2）if(isBadVersion(mid)):
               r=mid - 1

意思是mid值比目标值大了或者刚刚好相同，右指针向左移动

（3）else:

               l=mid + 1

其他情况就是mid值小于目标值，左指针向左移动

（4）最后返回 左指针的值是因为

    具体看这种特殊情况     因为当mid值小于目标值，是左指针动，所以返回左指针

动态演示如下

https://ucc.alicdn.com/images/user-upload-01/7722336420314a088b59ad12e6936cbc.gif

🍟代码

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l=1
        r=n
        while(l<=r):
            mid=(l+r)//2
            if(isBadVersion(mid)):
                r=mid - 1
            else:
                l=mid + 1
        return l

🍕题目三

35. 搜索插入位置

🍔思路：

（1）while(l < r)   因为采用左闭右开区间[left,right)右开， 所以不能有=,区间不存在

（2）

if nums[mid] < target:                 # 中点小于目标值,在右侧,可以得到相等位置

               l = mid + 1                    # 左闭,所以要+1

（3）right = mid                       # 右开,真正右端点为mid-1

（4）return left

# 此算法结束时保证left = right,返回谁都一样

和上面的第二题算法不同哦，因为区间选取不同

第二题，只能返回左指针

🍟代码：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)
        while(l < r):
            mid = (l+r)//2
            if(nums[mid]<target):
                l = mid + 1
            else:
                r = mid
        return l