二分查找

import java.util.*;
public class Solution {
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
//类似于求数组中第一个相等的数
    public int upper_bound_ (int n, int v, int[] a) {
        // write code here
        if(n==0||a[n-1]<v)return n+1;
        int low=0,high=n-1,mid=0;
        while(low<high){
//当求最后一个相等时:
//mid=low+(high-low+1)/2; 当a[mid]<=v时，low=mid;否则high=mid-1;
            mid=low+(high-low)/2;
            if(a[mid]>=v){
                high=mid;
            }else{
                low=mid+1;
            }
        }
        return high+1;
    }
}