中等难度-二分查找

来源于leetcode题库33,34,240

• 二分查找模版

- 模板1-再循环体中查找元素
思想：
  先看中间位置的元素，如果等于就返回中间位置的下标，
  否则看中间位置的元素的值与目标值的大小关系决定下一轮在哪一侧查找目标元素
  循环可以继续的条件是while(left<=right)
- 模板2-咋看循环体里排除不存在目标元素的区间
  难点是理解根据分支决定取中间数是上取整还是下取整，避免死循环
  基本思想：
    从考虑那些元素一定不是目标元素开始考虑
    循环可以继续的条件写为while(left<right),表示退出循环的时候[left,right]这个区间内只有一个元素，这可能就是目标元素
    写if和else语句的时候，思考当nums[mid]满足什么性质的时候，nums[mid]不是解，进而接着判断mid的左边有没有可能是解，右边有没有可能是解

33.

• 题目描述

  • 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
    ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
    搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
    你可以假设数组中不存在重复的元素。
    你的算法时间复杂度必须是 O(log n) 级别。

• 示例

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

• 题解

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            #如果mid指向target，直接返回mid
            if nums[mid] == target:
                return mid
            # 左半段有序
            if nums[mid] >= nums[left]:
                #如果target落在左侧
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                else:#反之target落在右侧
                    left = mid + 1
            # 右半段有序
            else:
                #如果target落在右侧
                if nums[mid] <= target <= nums[right]:
                    left = mid + 1
                else:#反之target落在左侧
                    right = mid - 1
        return -1

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

• 题目描述

  • 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
    你的算法时间复杂度必须是 O(log n) 级别。
    如果数组中不存在目标值，返回 [-1, -1]。

• 示例

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

• 题解

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if nums==[]:
            return [-1,-1]
        #找第一个位置，下取整实现
        left=0
        right=len(nums)-1
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]<target:
                left=mid+1
            else:
                right=mid
        if nums[left]!=target:  #如果找不到第一个位置，直接返回[-1,-1]即可
            return [-1,-1]
        a=left
        #找最后一个位置，上取整实现
        left=0
        right=len(nums)-1
        while left<right:
            mid=left+(right-left+1)//2
            if nums[mid]>target:
                right=mid-1
            else:
                left=mid
        b=left
        return [a,b]

240.搜索二维矩阵(二)

• 题目描述
  • 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
    每行的元素从左到右升序排列。
    每列的元素从上到下升序排列。

• 示例

现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

• 题解

class Solution:
    def searchMatrix(self, matrix, target):
        '''
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        '''
        # 暴力解法 -  二分解法暂未做出来
        for row in matrix:
            if target in row:
                return True
        
        return False