Leetcode: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]

思路：算法时间复杂度要求为O（log n），第一反应是二分法查找。

对于一般的情况：有序无重复数组nums，查找某一个target是否存在于nums中，若存在返回其index。

def main(nums,target):
    left = 0
    right = len(nums)-1
    #注意此处为<=，否则会漏查
    while(left<=right):
        mid = (left+right)//2
        if nums[mid] == target:
            return mid
        elif nums[mid]>target:
            right = mid-1
        else:
            left = mid+1
    return -1

下面介绍其变种：对于有序且存在重复的数组nums，给定target，分别返回

①第一个与target相等的index

②最后一个与target相等的index

③查找最后一个小于target的元素

④查找第一个大于target的元素

⑤查找最后一个小于或等于target的元素

⑥查找第一个大于或等于target的元素

上述情况以表格进行示意

nums（target=3）	1	2	3	3	3	4
变种		③	①		②	④
		⑤	或		⑤
			⑥	或		⑥

其中，①③分别代表一对left与right，②④分别代表一对right与left

以①③举例：

Leetcode:34二分法查找之在排序数组中查找元素的第一个和最后一个位置

本题①②程序：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 二分查找先判断数组是否为一维
        if len(nums)==1:
            return [-1,-1] if target!=nums[0] else [0,0]
        left = 0
        right = len(nums)-1
        while(left<=right):
            mid = (left+right)//2
            if nums[mid]>= target:
                right = mid-1
            else:
                left = mid+1
        #判断是否越界且相等
        if (left<len(nums) and nums[left]==target) is False:
            return [-1,-1]
        left_o = left
        
        #遍历
        # for i in range(left,len(nums)):
        #     if nums[i] == target:
        #         continue
        #     return [left,i-1]
        # return [left,len(nums)-1]
        
        left = 0
        right = len(nums)-1
        while(left<=right):
            mid = (left+right)//2
            if nums[mid]<=target:
                left = mid+1
            else:
                right = mid-1
        if right<len(nums) and nums[right]==target:
            right_o = right
        
        return [left_o,right_o]

①-⑥通解：

while (left <= right) {
    int mid = (left + right) / 2;
    if (array[mid] ? key) {
        //... right = mid - 1;
    }
    else {
        // ... left = mid + 1;
    }
}
return xxx;

若求第一个....返回left，若求最后一个....返回right。至于nums[mid] ? target，①③⑥为 nums[mid]>=target,②④⑤为nums[mid]<=target。

Leetcode:34二分法查找之在排序数组中查找元素的第一个和最后一个位置

相关推荐