leetcode(16)二分查找系列题目

69. x 的平方根

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        while left <= right:
            mid = (left + right) // 2
            if mid * mid == x:
                return mid
            elif mid * mid < x:
                left = mid + 1
            else:
                right = mid - 1
        return right  # 没找到则返回最大的一个平方小于x的即退出循环的right

633. 平方数之和

class Solution:
    def judgeSquareSum(self, c: int) -> bool:       
        i = 0
        while i*i <= c:
            i += 1
        left, right = 0, i
        while left <= right:
            sum_ =left*left + right*right
            if sum_ == c:
                return True
            elif sum_ < c:
                left += 1
            else:
                right -= 1
        return False

# 暴力法
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        nums = set()
        i = 0
        while i*i <= c:
            nums.add(i*i)
            i += 1
        # print(nums)
        for n in nums:
            if (c - n) in nums:
                return True
        
        return False

33. 搜索旋转排序数组

先判断左边有序且target在左边，则收缩右边界

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