2014年5月11日星期日

Binary Search Solution - Search for a Range

The idea is to define an array with size 2 to store lower and higher range. Implement binary search to locate the index.

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        if(A == null || A.length == 0){
            return res;
        }
        searchRangeOps(A, target, 0, A.length - 1, res);
        return res;
    }
   
    private void searchRangeOps(int[] A, int target, int begin, int end, int[] res){
        if(begin > end){
            return;
        }
        int mid = (begin + end) / 2;
        if(begin == end){
            if(A[begin] == target){
                if(begin < res[0] || res[0] == -1){
                    res[0] = begin;
                }
                if(end > res[1] || res[1] == -1){
                    res[1] = end;
                }
            }
            return;
        }
       
        if(target > A[mid]){
            searchRangeOps(A, target, mid + 1, end, res);
        }else if(target < A[mid]){
            searchRangeOps(A, target, begin, mid - 1, res);
        }else{
            int index1 = mid;
            int index2 = mid;
            while(index1 >= begin && A[index1] == target){
                index1--;
            }
            while(index2 <= end && A[index2] == target){
                index2++;
            }
            index1++;
            if(index1 < res[0] || res[0] == -1){
                res[0] = index1;
            }
            index2--;
            if(index2 > res[1] || res[1] == -1){
                res[1] = index2;
            }
            return;
            // if(mid < res[0] || res[0] == -1){
            //     res[0] = mid;
            // }
            // if(mid > res[1] || res[1] == -1){
            //     res[1] = mid;
            // }
            //searchRangeOps(A, target, begin, mid - 1, res);
            //searchRangeOps(A, target, mid + 1, end, res);
        }
    }
}

没有评论: