Binary search

通用写法

public int findPosition(int[] nums, int target){
    if(nums == null || nums.length == 0 ){
        return -1;
    }   
    int start = 0,end = nums.length-1;
    while(start+1<end){
         //等价于(start + end)/2,但这么写防溢出
        int mid = start+(end-start)/2;
        if(nums[mid] == target){
            //不直接返回是因为若题目要求返回第一个出现的，则需继续进行比较而不能马上返回，此时令end=mid，反之若要求最后一个出现的，则令start=mid;
            end =mid;
        }else if(nums[mid]<target){
            start = mid;
        }else{
            end = mid;
        }
    }
    //若是要第一个出现的则先比较start，若要最后一个则就要先比较end
    if(nums[start] == target){
        return start;
    }
    if(nums[end] == target){
        return end;
    }
    return -1;
}

转载于:https://www.jianshu.com/p/3a179a8aa268