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

本文介绍: 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

方法一、二分查找法

题目要求时间复杂度为 O(log n) ，首先想到的是二分查找法。
起始位置：查找target第一次出现的位置，一直找到不满足target <= nums[mid]为止。但是结束位置如何找呢？
结束位置：找第一个大于target的值的位置，然后前一个位置就是目标值的结束位置。

Swift

/*
     1.开始位置即为target第一次出现的位置，二分查找即可
     2.结束位置为第一个大于target的位置-1
     3.校验索引是否满足条件及越界检查等
     */
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        
        //开始位置
        let left = binarySearch(nums, true, target)
        
        //结束位置
        let right = binarySearch(nums, false, target)-1
        
        //校验
        if left <= right && right<nums.count && (nums[left] == nums[right]) {
            return [left, right]
        }
        
        return [-1, -1]
    }
    
    //二分查找target在nums中的索引，lower为true表示查找第一个大于等于target的索引
    func binarySearch(_ nums: [Int], _ lower: Bool, _ target: Int) -> Int {
        var left = 0, right = nums.count - 1, ans = nums.count
        
        while left <= right {
            let mid = (left + right) >> 1
            
            if target < nums[mid] || (lower && target <= nums[mid]) {
                right = mid - 1
                ans = mid
            }else {
                left = mid + 1
            }
        }
        return ans
    }

OC

//非严格递增的序列中查找target的起始位置
-(NSArray *)searchRange:(NSArray <NSNumber *>*)nums
                 target: (NSInteger)target {
    NSInteger leftIdx = [self binarySearch:nums lower:YES target:target];
    NSInteger rightIdx = [self binarySearch:nums lower:NO target:target];
    
    if (leftIdx <= rightIdx && rightIdx<nums.count && ([nums[leftIdx] integerValue] == [nums[rightIdx] integerValue])) {
        return @[@(leftIdx), @(rightIdx)];
    }
    
    return @[@-1, @-1];
}


/// 二分查找，在nums数组中大于或大于等于target的第一个索引位置
/// - Parameters:
///   - nums: 有序数列
///   - lower: 为true表示大于等于target的索引，为false表示大于target的索引
///   - target: 目标值
- (NSInteger)binarySearch:(NSArray *)nums lower:(BOOL)lower target:(NSInteger)target {
    NSInteger left = 0, right = nums.count-1;
    NSInteger ans = nums.count;
    
    while (left <= right) {
        NSInteger mid = (left + right) >> 1;
        
        if (target < [nums[mid] integerValue] || (lower && target <= [nums[mid] integerValue])) {
            right = mid - 1;
            ans = mid;
        }else {
            left = mid + 1;
        }
    }
    
    return ans;
}