二分查找

題目描述

請實現(xiàn)有重復數(shù)字的有序數(shù)組的二分查找。

輸出在數(shù)組中第一個大于等于查找值的位置，如果數(shù)組中不存在這樣的數(shù)，則輸出數(shù)組長度加一。

示例

輸入

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

返回值

3

說明

輸出位置從1開始計算 

題目答案

很簡單的二分查找，關鍵看三個地方就行了：

• low < high 還是low <= high
• mid是左傾還是右傾
• 向左收縮條件及向右收縮條件

import java.util.*;


public class Solution {
    /**
     * 二分查找
     * @param n int整型 數(shù)組長度
     * @param v int整型 查找值
     * @param a int整型一維數(shù)組 有序數(shù)組
     * @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;
    }
}