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=res==-1?mid:Math.min(res,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=res==-1?mid:Math.max(res,mid);
}
}
return res;
}
}