剑指 Offer 53 - I. 在排序数组中查找数字 I

   很明显，遍历一遍数组，用O(N)的时间复杂度是可以做出来的，但是我们在做这种排序数组的题目中，可以用二分法把时间复杂度降低到O(logN)。

　　但是我们会发现，正常的二分查找法是查找数组里是否有某个数，那么我们就不能用普通的二分查找，而需要使用二分查找来查找边界。我们可以返回target的右边界（第一个大于target数的索引）和target-1的右边界，然后相减就可以得到对应的元素个数。

class Solution {
    public int search(int[] nums, int target) {
        return findRight(nums,target) - findRight(nums,target-1);
    }
    public int findRight(int[] nums,int target){
        int low = 0,high = nums.length-1,mid;
        while(low<=high){
            mid = (low+high)/2;
            if(nums[mid] <= target){
                //向右边找
                low = mid + 1; //low最终位置在重复元素的右边
            }else{
                high = mid - 1;
            }
        }
        return low;
    }
}

　　由于 high 的初始化条件是 nums.length-1，因此二分查找的搜索范围是 [low,high]。修改条件对应的是 low = mid + 1，high = mid - 1。而我们需要返回右边界，因此while循环的退出条件应该是 low == high + 1，即 while(low<=high)，此时low对应的就是target的右边界。

　　另外一个必须要注意的地方：当nums[mid] == target 的时候，我们不需要返回数值，因为我们需要的是右边界。这时候做的操作是 low = mid + 1，继续往右边搜索，直到找到第一个比target大的元素。