Binary Search

模板：

//end condition of while loop is start+1<end



public class Solution{


    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){
            int mid = start + (end -start )/2
            if (nums[mid] == target) {
                return mid;
            }
            else if(nums[mid] < target){
                start = mid;
            }else{
                end = mid;
            }
        }


        //double check 退出的时候 start和end是相邻的关系 有可能此时还没有找到target
        //这个时候范围已经缩小到了两个 一个end 一个start，所以判断一下这两个就好，类似递归的思想，不断缩小问题范围
        if (nums[start] == target) {
            return start;
        }

        if (nums[end] == target) {
            return end;
        }

        return -1;
    }
}