來源于leetcode題庫33,34,240

• 二分查找模版

- 模板1-再循環(huán)體中查找元素
思想：
  先看中間位置的元素，如果等于就返回中間位置的下標，
  否則看中間位置的元素的值與目標值的大小關系決定下一輪在哪一側查找目標元素
  循環(huán)可以繼續(xù)的條件是while(left<=right)
- 模板2-咋看循環(huán)體里排除不存在目標元素的區(qū)間
  難點是理解根據(jù)分支決定取中間數(shù)是上取整還是下取整，避免死循環(huán)
  基本思想：
    從考慮那些元素一定不是目標元素開始考慮
    循環(huán)可以繼續(xù)的條件寫為while(left<right),表示退出循環(huán)的時候[left,right]這個區(qū)間內只有一個元素，這可能就是目標元素
    寫if和else語句的時候，思考當nums[mid]滿足什么性質的時候，nums[mid]不是解，進而接著判斷mid的左邊有沒有可能是解，右邊有沒有可能是解

33.

• 題目描述

  • 假設按照升序排序的數(shù)組在預先未知的某個點上進行了旋轉。
    ( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
    搜索一個給定的目標值，如果數(shù)組中存在這個目標值，則返回它的索引，否則返回 -1 。
    你可以假設數(shù)組中不存在重復的元素。
    你的算法時間復雜度必須是 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.在排序數(shù)組中查找元素的第一個和最后一個位置

• 題目描述

  • 給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標值 target。找出給定目標值在數(shù)組中的開始位置和結束位置。
    你的算法時間復雜度必須是 O(log n) 級別。
    如果數(shù)組中不存在目標值，返回 [-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]
        #找第一個位置，下取整實現(xiàn)
        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
        #找最后一個位置，上取整實現(xiàn)
        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。該矩陣具有以下特性：
    每行的元素從左到右升序排列。
    每列的元素從上到下升序排列。

• 示例

現(xiàn)有矩陣 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