二分查找

牛客题霸NC105

难度：Easy

题目描述

请实现有重复数字的有序数组的二分查找。

输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。

示例

输入

5,4,[1,2,4,4,5]

返回值

3

说明

输出位置从1开始计算 

题目答案

很简单的二分查找，关键看三个地方就行了：

• low < high 还是low <= high
• mid是左倾还是右倾
• 向左收缩条件及向右收缩条件

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

        return a[low] >= v ? low + 1 : n + 1;
    }
}