import java.util.*;
/**
*题目：请实现有重复数字的有序数组的二分查找。
*输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
*
*解题思路：
采用二分查找的思想解决问题，首先用两个指针标记左、右，然后用mid所指的位置与关键字比较。
若小于关键字，则在其右侧继续二分查找；
若大于等于关键字，且其左邻元素也大于等于该关键字，则继续在mid的左侧二分查找，否则输出mid+1.
若遍历后不存在这样的值，输出n+1。
*/
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] >= v){
j = mid - 1;
mid = (i+j)/2;
}
else{
return mid + 1;
}
}
return n + 1;
}
}
