Leetcode 34. Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array :

給定一個遞增排列的整數數組 nums，找到給定目標值的開始和結束位置。

如果在數組中找不到目標，則返回 [-1, -1]。

O(log n) 時間複雜度內

Python

方法 : 做兩次binary Search

class Solution(object):
    def searchRange(self, nums, target):
        left=self.firstans(nums,target)
        right=self.lastans(nums,target)
        if left==right:          #兩個相等的時候代表沒有找到
            return[-1,-1]
        return [left,right-1]

    def firstans(self,nums,target):
        left,right=0,len(nums)
        while left<right:
            mid=left+(right-left)/2
            if nums[mid]<target:
                left=mid+1       #往右半邊移動
            else:
                right=mid        #往左半邊移動
        return left
    
    def lastans(self,nums,target):
        left,right=0,len(nums)
        while left<right:
            mid=left+(right-left)/2
            if nums[mid]<=target:
                left=mid+1        #往右半邊移動
            else:
                right=mid         #往左半邊移動
        return left

C++

二分查找法:

左右逼近，直到找到等於target的數，但可能有重複的target在nums裡面，所以也要考慮。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                if (nums[left] < target) {
                    left++;
                }
                if (nums[right] > target) {
                    right--;
                }
                if (nums[left] == nums[right]) {
                    return {left, right};
                }
            }
        }
        return {-1, -1};
    }
};