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

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

Problem Analysis:

Because the nums is sorted, so we can use bisection method to find the first index that equal the target, then first index that greater the target. So it is the range value we wanted.

If you are familiar with c++ stl, you can imitate the lower_bound and upper_bound to get the range.

Solution

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {          
        int start = 0;
        int len = nums.size();
        while (len > 0) {
            int half = len >> 1;
            int mid = start + half;
            if (nums[mid] < target) {
                start = mid + 1;
                len = len - half - 1;
            } else {
                len = half;
            }
        }
        
        if (start == nums.size() || nums[start] != target) return {-1, -1};
        
        int end = 0;
        len = nums.size() ;
        while (len > 0) {
            int half = len >> 1;
            int mid = end + half;
            if (nums[mid] > target) {
                len = half;
            } else {
                end = mid + 1;
                len = len - half - 1;
            }
        }
        
        return {start, end - 1};
    }
};

time complexity is O(log)

Space complexity is O(1)