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

Description

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

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

Follow up: Could you write an algorithm with O(log n) runtime complexity?

Constraints

• 0 <= nums.length <= 105

• -109 <= nums[i] <= 109

• nums is a non-decreasing array.

• -109 <= target <= 109

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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]

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        if(nums == null || nums.length == 0) return result;
        int index = binarySearch(nums, target, 0, nums.length-1);
        if(index == -1) return result;
        result[0] = index;
        result[1] = index;
        int i = index;
        while(i > 0 && nums[i-1] == target) {
            i = binarySearch(nums, target, 0, i-1);
            if(result[0] == i) break;
            if(i != -1) result[0] = i;
        }
        i = index;
        while(i < nums.length-1 && nums[i+1] == target) {
            i = binarySearch(nums, target, i+1, nums.length);
            if(result[1] == i) break;
            if(i != -1) result[1] = i;
        }
        return result;
    }
    
    private int binarySearch(int[] nums, int target, int low, int high) {
        while(low <= high) {
            int mid = (low+high)/2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] < target) {
                low = mid+1;
            } else {
                high = mid-1;
            }
        }
        return -1;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if(nums == null || nums.length == 0) {
            return result;
        }
        
        int n = nums.length;
        int index = binarySearch(nums, target, 0, n-1);
        
        if(index >= 0) {        
            int lower = index;
            while(lower > 0 && nums[lower-1] == target) {
                int tmpIdx = binarySearch(nums, target, 0, lower-1);
                if(tmpIdx >= 0) {
                    lower = tmpIdx;
                } else {
                    break;
                }
            }
            result[0] = lower;

            int higher = index;
            while(higher < n-1 && nums[higher+1] == target) {
                int tmpIdx = binarySearch(nums, target, higher+1, n-1);
                if(tmpIdx >= 0) {
                    higher = tmpIdx;
                } else {
                    break;
                }
            }
            
            result[1] = higher;
        }
        
        return result;
    }
    
    private int binarySearch(int[] nums, int target, int low, int high) {
        while(low <= high) {
            int mid = low + (high-low)/2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

Follow up