Leetcode 二分查找专辑

33. Search in Rotated Sorted Array

在一个旋转的有序数组中寻找指定数字,确保数组中元素不重复。
核心方案是二分,具体思路是先把问题拆分开,找到旋转点所处的区间。
如果 nums[mid] < nums[l],则说明左侧是断开的,右侧是连续的,旋转点在左侧。此时,根据 nums[mid] < target <= nums[r] 来判断 target 是否位于右侧的连续区间内。如果符合,则 l = mid + 1 。注意右侧的等于号,包括了 nums[r] 即为 target 的情况。

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

81. Search in Rotated Sorted Array II

前面一道题的延伸版本,在一个旋转的有序数组中寻找指定数字,数组中元素可能重复。

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

34. Find First and Last Position of Element in Sorted Array

寻找有序数组中元素的左右边界。
思路是两次二分,第一次找左边界,第二次找右边界。
注意:

  • 寻找左边界的时候,l 从 -1 开始,然后取 r 作为左边界
  • 寻找右边界的时候,r 从 len(nums) 开始,然后取 l 作为右边界
    这样的好处是,妥善的解决了 0 和 len(nums)-1 位置就是 target 的情况
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]
        L = None
        R = None
        
        l = -1
        r = len(nums) - 1
        while l < r - 1:
            mid = l + (r-l) // 2
            if nums[mid] < target:
                l = mid
            else:
                r = mid
        if nums[r] == target:
            L = r
        else:
            return [-1, -1]
            
        l = 0
        r = len(nums)
        while l < r - 1:
            mid = l + (r-l) // 2
            if nums[mid] <= target:
                l = mid
            else:
                r = mid
        
        if nums[l] == target:
            R = l
        else:
            return [-1, -1]
            
            
        return [L, R]

50. Pow(x, n)

二分查找计算数字的 n 次幂。
注意这里要判断 n < 0 和 n == 0 的情况。
递归写法可以将 n 做 -n 和 n-1 处理后继续运算,确保 n 为偶数时 x*x^ n/2 即可。

# 递归
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            return self.myPow(1/x, -n)
        if n == 0:
            return 1
        if n %2 == 1:
            return x * self.myPow(x, n-1)
        return self.myPow(x*x, n//2)

# 非递归
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1/x
            n = -n
        
        result = 1
        
        while n > 0:
            if n % 2 == 1:
                n -= 1
                result = result * x
            else:
                n = n //2
                x = x * x
        
        return result

69. Sqrt(x)

计算数字 x 的平方根。
根据 mid2、(mid+1)2 和 x 三者的大小关系调整 l 与 r 的值。

class Solution:
    def mySqrt(self, x: int) -> int:
        l = 0
        r = x
        while l <= r:
            mid = l + (r-l) // 2
            if mid**2 > x:
                r = mid
            else:
                if x < (mid+1)**2:
                    return mid
                l = mid + 1

162. Find Peak Element

寻找数组中的峰值。
只要 mid < mid+1 就不断的 l = mid + 1,这样可以确保 l 是目前的极大值。

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