Search for a Range

Q:
Given a sorted array of integers, 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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

A:   就是简单的二分查找，利用个数组的low，high两个index来找



--------------第二遍--------
就是对于找 findLast的时候，   对于边界问题，没考虑好 -----------回头，仔细琢磨吧

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int start = findFirst(A,0,A.length -1,target);
        if(start <0){
            int result[] = {-1,-1};            
            return result;
        }
        int end = findLast(A,start, A.length-1, target);
        int[] result = {start, end};
        return result;
    }
    
    private int findFirst(int[] A, int begin, int end, int target){
        if(begin > end)
            return -1;
            
        if(begin == end){
            if(A[begin] == target){
                return begin;
            }else{
                return -1;
            }
        }
        int mid = (begin+end)/2;
        if(A[mid]>=target){
            return findFirst(A,begin,mid,target);
        }else{ 
            return findFirst(A,mid+1,end,target);
        }
    }
    private int findLast(int[] A, int begin, int end, int target){
        if(begin > end)
            return -1;
        if(begin == end){
            if(A[end] == target){
                return end;
            }else{
                return -1;
            }
        }
        int mid = (begin+end +1)/2;
        if(A[mid]<= target){
            return findLast(A,mid,end,target);
        }else{
            return findLast(A,begin,mid-1,target);
        }
    }
}

----------------3rd pass-----------------------------------

public class Solution { 
    public int[] searchRange(int[] nums, int target) {
        int res[] = {helper(0,nums.length-1, nums,target,true),helper(0,nums.length-1,nums,target,false)};
        return res;
    }
    private int helper(int start, int end, int[] A, int target, boolean isMin){
        if( start > end)
            return -1;
        int mid = (start+end)/2;
        if( A[mid]==target){
            if(isMin){ // need check left
                int left = helper(start,mid-1, A, target, isMin);
                return left>=0?left:mid;
            }else{
                int right = helper(mid+1, end, A, target, isMin);
                return right>=0?right : mid;
            }
        }else if(A[mid] < target){
            return helper(mid+1,end, A,target, isMin);
        }else{
            return helper(start,mid-1,A,target,isMin);
        }
    }
} 

Learned: