34. Search for a Range

题目描述

Given an array of integers 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 ofO(logn).

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

For example,
Given[5, 7, 7, 8, 8, 10]and target value 8,
return[3, 4].

解题方法

這題是透過Binary search 找範圍． 所以我們可以用first/last position 思路去解題

public int[] searchRange(int[] nums, int target) {
        //Corner case
        if(nums == null || nums.length == 0){
            return new int[]{-1, -1};
        }

        int start = 0, end = nums.length - 1;
        int[] bound = new int[2];

        //Check first occurance
        while(start + 1 < end){
            int mid = start + (end - start) / 2; //avoid overflow
            if(nums[mid] == target){                                       //**********
                end = mid;
            }else if(nums[mid] < target){
                start = mid;
            }else{
                end = mid;
            }
        }

        if( nums[start] == target){
            bound[0] = start;                                             //**********
        }else if( nums[end] == target){
            bound[0] = end;
        }else{
            bound[0] = -1;
        }

        start = bound[0];
        end = nums.length - 1;
        //Check last occurance
        while( start + 1 < end){
            mid = start + (end - start)/2;
            if(nums[mid] == target){
                start = mid;
            }else if(nums[mid] < target){
                start = mid;
            }else{
                end = mid;
            }
        }

        if( nums[end] == target){
            bound[1] = end;
        }else if( nums[start] == target){
            bound[1] = start;
        }else{
            bound[1] = -1;
        }

        return bound;

    }