Description

LeetCode 34

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

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]

Analysis

It is easy to come up with binary search. However, how do we solve the condition that the middle element equals to the target?

At the beginning, I just use binary search for both sides. I found the mistake soon. The problem asks us to implement a \(O(logn)\) algorithm. But if binary search is used for both sides, then the worst case time is \(O(n)\).

In fact, the correct solution is not difficult. Just find the starting position and ending position respectively by controlling the equal condition. The time will become \(O(logn)\).

Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res=new int[]{-1,-1};
        if(nums.length==0) return res;
        int low=0,high=nums.length-1;
        while(low<=high)
        {
            int mid=(high-low)/2+low;
            if(target<=nums[mid]) 
            {
                high=mid-1;
                if(target==nums[mid])
                    res[0]=res[0]==-1?mid:Math.min(res[0],mid);
            }
            else low=mid+1;
        }
        low=0;
        high=nums.length-1;
        while(low<=high)
        {
            int mid=(high-low)/2+low;
            if(target<nums[mid]) high=mid-1;
            else 
            {
                low=mid+1;
                if(target==nums[mid])
                    res[1]=res[1]==-1?mid:Math.max(res[1],mid);
            }
        }
        return res;
    }
}

Reference

[1] https://www.geeksforgeeks.org/find-first-and-last-positions-of-an-element-in-a-sorted-array/

Leave a Reply

Your email address will not be published. Required fields are marked *