14二分查找

1 注意比较的时候比较的是值还是下标
2 startIndex>=endIndex,第一次写成了<=
3 数组中有多个重复值得时候怎么办,写进一个list里

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        if(nums==null||nums.length==0||target<nums[0]||target>nums[nums.length-1]){
            return -1;
        }
        int startIndex=0;
        int endIndex=nums.length-1;
        int middleIndex;
        ArrayList indexList=new ArrayList();
        while(true){
            middleIndex=(startIndex+endIndex)/2;
            if(nums[middleIndex]==target){
                indexList.add(middleIndex);
            }
            if(startIndex>=endIndex){
                if(indexList.size()==0)
                    return -1;
                else
                    return (int)indexList.get(indexList.size()-1);
            }else{
                if(target<=nums[middleIndex]){
                    endIndex=middleIndex-1;
                }else{
                    startIndex=middleIndex+1;
                }
            }
        }
    }
}