二分查找

解题思路：采用二分查找的思想解决问题，首先用两个指针标记左、右，然后用mid所指的位置与关键字比较。若小于关键字，则在其右侧继续二分查找；若大于等于关键字，且其左邻元素也大于等于该关键字，则继续在mid的左侧二分查找，否则输出mid+1.若遍历后不存在这样的值，输出n+1。

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
        int i=0;
        int j=n-1;
        int mid=(i+j)/2;
        while(i<=j){
            if(a[mid]<v){
                i=mid+1;
                mid=(i+j)/2;
            }
            else if(mid>0&&a[mid-1]>=v){
                j=mid-1;
                mid=(i+j)/2;
            }
            else{
                return mid+1;
            }
        }
        return n+1;
    }
}