【经典LeetCode算法题目专栏分类】【第6期】二分查找系列：x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值

class Solution:

    def mySqrt(self, x: int) -> int:

        l, r, ans = 0, x, -1

        while l <= r:

            mid = (l + r) // 2

            if mid * mid <= x:

                ans = mid

                l = mid + 1

            else:

                r = mid - 1

        return ans

class Solution:

    def isPerfectSquare(self, num: int) -> bool:

        l = 0

        r = num

        while l <= r:

            mid = (l+r)//2

            if mid * mid == num:

                return True

            elif mid * mid < num:

                l = mid + 1

            else:

                r = mid - 1

        return False

class Solution:

    def search(self, nums: List[int], target: int) -> int:

        if not nums:

            return -1

        # 二分法

        n = len(nums)

        left = 0

        right = n - 1

        while left <= right:

            mid = (left + right) // 2

            if nums[mid] == target:

                return mid

            if nums[0] <= nums[mid]:

                # 说明左边有序

                if nums[0] <= target < nums[mid]:

                    right = mid - 1

                else:

                    left = mid + 1

            else:

                # 右边有序

                if nums[mid] < target <= nums[n-1]:

                    left = mid + 1

                else:

                    right = mid - 1

        return -1

class Solution:

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

        if not matrix:

            return False

        # 二分查找 row = index // n ; col = index % n

        m = len(matrix)

        n = len(matrix[0])

        left = 0

        right = m * n - 1

        while left <= right:

            mid = (left + right) // 2

            cur_m = mid // n

            cur_n = mid % n

            if matrix[cur_m][cur_n] == target:

                return True

            elif matrix[cur_m][cur_n] > target:

                right = mid - 1

            else:

                left = mid + 1

        return False

   def searchMatrix(self, matrix, target):

        """

        :type matrix: List[List[int]]

        :type target: int

        :rtype: bool

        """

        # 1.暴力法 for i in range(m) for j in range(n)   O(mn)

        # 2.剪枝搜索，假设从左下角开始搜索O(m+n)

        if not matrix:

            return False

        m = len(matrix)

        n = len(matrix[0])

        row = m - 1

        col = 0

        while row >= 0 and col < n:

            if matrix[row][col] > target:

                row -= 1

            elif matrix[row][col] < target:

                col += 1

            else:

                return True

        return False

class Solution:

    def findMin(self, nums: List[int]) -> int:

        if len(nums) == 1:

            return nums[0]

        left = 0

        right = len(nums) - 1

        while left < right:

            mid = (left + right) // 2

            if nums[mid] < nums[right]:

                # mid可能是最小值

                right = mid

            else:

                # mid一定不是最小值

                left = mid + 1

        return nums[left]