基础算法题总结4--二分查找

二分查找

基本写法

def binarySearch(nums,target):
    n = len(nums)
    left,right = 0,n-1
    mid = (left + right) // 2 ## 取中心
    while left <= right:
        if nums[mid] == target:
            return mid
        if nums[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    return -1

相关练习

LeetCode中相关的题目：

• 33.搜索旋转排序数组: 二分查找，一半有序，另一半半有序
• 34.在排序数组中查找元素的第一个和最后一个位置

题目详细描述

搜索旋转排序数组：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left = 0
        right = n-1
        while(left <= right): 
            mid = (left + right) // 2 ## 取中心
            if nums[mid] == target: ## 当找到就返回所在的下标
                return mid
            ## 当[l,mid-1]是有序数组的时候 0表示最左侧，也可以使用left
            if nums[0] <= nums[mid]: 
                ## 如果target在[0,mid]中，则在[l,mid-1]中查找
                if nums[0] <= target < nums[mid]: 
                    right  = mid - 1
                else: ## 否则在[mid+1,r]中查找
                    left = mid + 1
            else: ## 当[mid, r] 是有序数组的时候, n-1表示最右侧，也可以使用right
                ## 如果target在[mid+1,r]中，则在[mid+1,r]中查找
                if nums[mid] <  target <= nums[n-1]: 
                    left = mid + 1
                else: ## 否则在[l,mid-1]中查找
                    right = mid - 1
        return -1