Find First and Last Position of Element in Sorted Array

Question: Given an array of integers nums sorted in ascending order, find the starting and ending position of a given targetvalue.

Your algorithm’s runtime complexity must be in the order of O(log n).

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

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]

You may view the full question here.

Approach 1: Let’s start with something simple —

//Approach 1:
//Runtime: 0ms
//Memory usage: 43.9MB
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = -1, end = -1;
        for(int i = 0; i<nums.length; i++){
            if(nums[i]==target){
                start=i;
                break;
            }
        }
        
        for(int i = nums.length-1; i>=0; i--){
            if(nums[i]==target){
                end=i;
                break;
            }
        }
        return new int[]{start, end};
    }
}

Approach 2: Let’s adopt binary search to make the search more efficient —

//Approach 2:
//Runtime: 0ms
//Memory usage: 44.2MB
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        
        int mid;
        int first = -1;
        while(start<=end){
            mid = (start+end)/2;
            if(nums[mid]==target){
                first = mid;
                break;
            }
            if(target<nums[mid]){
                end = mid-1;
            } else {
                start = mid+1;
            }
        }
        if(first!=-1){
            for(start = first; start>0 && nums[start-1]==target;start--);
            for(end = first; end<nums.length-1 && nums[end+1]==target;end++);
            return new int[]{start, end};
        }
        return new int[]{-1,-1};
    }
}

Find more posts here.

Cheers & Chao!