二分查找：

二分法写法：

二分法的写法共分两种分别是：1.定义target在左闭右闭区间 2.定义target在左闭右开区间。
方法1. 定义target在左闭右闭区间，即[left, right]
1.while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=。
2.if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle – 1。

方法2. 定义target在左闭右闭区间，即[left, right)
1.while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的。
2.if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]。

二分法力扣相关题目：

35.搜索插入位置
34.在排序数组中查找元素的第一个和最后一个位置
69.x 的平方根
367.有效的完全平方数

答案与解析：

35.搜索插入位置

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

解析

要在数组中插入目标值总共有四种情况：
1.目标值在数组所有元素之前
2.目标值等于数组中某一个元素
3.目标值插入数组中的位置
4.目标值在数组所有元素之后

python 代码

方法1

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right=0, len(nums)-1  #左闭右闭区间

        while left <= right:
            middle=left+(right-left)//2
            if nums[middle]>target:
                right=middle-1
            elif nums[middle]<target:
                left=middle+1
            else:
                return middle
        return right+1

方法2：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right=0, len(nums)  #左闭右开区间
        while left < right:
            middle = left+(right-left)//2
            if nums[middle]>target:
                right=middle
            elif nums[middle]<target:
                left=middle+1
            else:
                return middle
        return right

34.在排序数组中查找元素的第一个和最后一个位置

题目：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

解析

寻找target在数组里的左右边界，有如下三种情况：
情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

python 代码

方法1：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def getRightBoder(nums,target):
            left, right = 0, len(nums)-1
            rightboder=-2
            while left <= right:
                middle = left+(right-left)//2
                if nums[middle]>target:
                    right=middle-1
                else:
                    left=middle+1
                    rightboder=left
                
            return rightboder

        def getLeftBoder(nums,target):
            left, right = 0, len(nums)-1
            leftboder=-2
            while left <= right:
                middle = left+(right-left)//2
                if nums[middle]>=target:
                    right=middle-1
                    leftboder=right
                else:
                    left=middle+1
                
            return leftboder

        leftboder=getLeftBoder(nums,target)
        rightboder=getRightBoder(nums,target)

        #情况一
        if leftboder==-2 or rightboder==-2: return [-1,-1]
        #情况三
        if rightboder-leftboder>1: return [leftboder+1,rightboder-1]
        #情况二
        return [-1,-1]

方法2：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearch(nums,target):
            left, right = 0, len(nums)-1
            while left <= right:
                middle = left+(right-left)//2
                if nums[middle]>target:
                    right=middle-1
                elif nums[middle]<target:
                    left=middle+1
                else:
                    return middle
            return -1

        index=binarySearch(nums,target)
        #情况一，情况二
        if index==-1: return [-1,-1]
        #情况三
        left, right = index, index
        while left-1 >0 and nums[left-1]==target: left-=1
        while right+1 < len(nums) and nums[right+1]==target: right+=1
        return [left,right]

69.x 的平方根

题目：给你一个非负整数 x ，计算并返回 x 的算术平方根 。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

python 代码

方法：

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right, ans=0,x,-1
        while left <= right:
            middle=left+(right-left)//2
            if middle * middle <= x:
                ans = middle
                left = middle+1
            else:
                right = middle-1
        return ans

367.有效的完全平方数

题目：给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

方法：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right=0,num
        while left<=right:
            middle = left+(right-left)//2
            square = middle*middle
            if square > num:
                right=middle-1
            elif square < num:
                left=middle+1
            else:
                return True
        return False
        

最后

以上就是谨慎云朵为你收集整理的力扣算法题总结（python）—二分查找二分查找：二分法力扣相关题目：答案与解析：的全部内容，希望文章能够帮你解决力扣算法题总结（python）—二分查找二分查找：二分法力扣相关题目：答案与解析：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。