Leetcode题解-算法-二分法(python版)

╰+哭是因爲堅強的太久メ 2022-10-15 01:53 140阅读 0赞

### 文章目录 ###

*   *  1、求开方
     *  2、找大于给定字符的最小字符
     *  3、排序重复数组中找出现一次的数
     *  4、第一个出错的版本
     *  5、旋转数组最小值
     *  6、目标数在排序数组中出现的首尾位置

## 1、求开方 ##

[69. x 的平方根(Easy)][69. x _Easy]

class Solution(object):
        def mySqrt(self, x):
            left, right = 1, x
            while (left <= right):
                mid = (left + right) // 2
                if mid * mid <= x:
                    left = mid + 1
                else:
                    right = mid - 1
            return right

## 2、找大于给定字符的最小字符 ##

[744. 寻找比目标字母大的最小字母(Easy)][744. _Easy]

class Solution(object):
        def nextGreatestLetter(self, letters, target):
            left, right = 0, len(letters) - 1
            while left <= right:
                mid = (left + right) // 2
                if letters[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return letters[0] if left == len(letters) else letters[left]

class Solution(object):
        def nextGreatestLetter(self, letters, target):
            index = bisect.bisect(letters, target)
            return letters[index%len(letters)]

## 3、排序重复数组中找出现一次的数 ##

[540. 有序数组中的单一元素(Medium)][540. _Medium]  
问题分析：  
二分法，每次让 mid 位于序号为 0,2,4,6… 的偶数的元素上。  
如果目标元素在 mid 右边,一定有 nums\[mid\]==nums\[mid+1\]，目标元素范围更新为 \[mid+2,right\]；  
如果目标元素为 mid 或者在 mid 左边，一定有 nums\[mid\]!=nums\[mid+1\]，目标元素范围更新为 \[left,mid\]。

class Solution(object):
        def singleNonDuplicate(self, nums):
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right) // 2
                if mid % 2:
                    mid -= 1
                if nums[mid] == nums[mid + 1]:
                    left = mid + 2
                else:
                    right = mid
            return nums[left]

时间复杂度：O(log(n/2)) = O(logn)，对元素的一半进行二分搜索。  
空间复杂度：O(1)

## 4、第一个出错的版本 ##

[278. 第一个错误的版本(Easy)][278. _Easy]

# The isBadVersion API is already defined for you.
    # @param version, an integer
    # @return a bool
    # def isBadVersion(version):
    
    class Solution(object):
        def firstBadVersion(self, n):
            left, right = 1, n
            while left < right:
                mid = (left + right)//2
                if isBadVersion(mid):
                    right = mid
                else:
                    left = mid + 1
            return left

## 5、旋转数组最小值 ##

[153. 寻找旋转排序数组中的最小值(Medium)][153. _Medium]

旋转之后，右侧的数据一定小于左侧的数据，如果 nums\[mid\]>nums\[right\]，则最小值在 mid 右侧，新的区间更新为 \[mid+1,right\]， nums\[mid\]<nums\[right\]，则最小值在 mid 及 mid 左侧，区间更新为 \[left,mid\]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5amFjb2I_size_16_color_FFFFFF_t_70]

class Solution(object):
        def findMin(self, nums):
            left, right = 0, len(nums)-1
            while left < right:
                mid = (left + right)//2
                if nums[mid] > nums[right]:
                    left = mid + 1
                else:
                    right = mid
            return nums[left]

## 6、目标数在排序数组中出现的首尾位置 ##

[34. 在排序数组中查找元素的第一个和最后一个位置(Medium)][34. _Medium]  
  
先找第一个大于等于 target 的元素下标，再找第一个大于等于 target+1 的元素下标

class Solution(object):
        def searchRange(self, nums, target):
        
            def insert_index(nums, x):
                left, right = 0, len(nums)
                while left < right:
                    mid = (left + right) // 2
                    if nums[mid] < x:
                        left = mid + 1
                    else:
                        right = mid
                return left
    
            if not nums or target > nums[-1]:
                return [-1, -1]
            low = insert_index(nums, target)
            if target != nums[low]:
                return [-1, -1]
            high = insert_index(nums, target + 1) - 1
            return [low, high]

[69. x _Easy]: https://leetcode-cn.com/problems/sqrtx/
[744. _Easy]: https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/
[540. _Medium]: https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
[278. _Easy]: https://leetcode-cn.com/problems/first-bad-version/
[153. _Medium]: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5amFjb2I_size_16_color_FFFFFF_t_70]: /images/20221014/16edd2e29f8149a999e3563c847e2303.png
[34. _Medium]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/