每天刷一道牛客题霸-第3天-二分查找

题目

https://www.nowcoder.com/practice/7bc4a1c7c371425d9faa9d1b511fe193?tpId=190&&tqId=35227&rp=1&ru=/ta/job-code-high-rd&qru=/ta/job-code-high-rd/question-ranking

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

        }
        if(a[index] == v){
            while(index >= 0 && a[index] == v){
                index--;
            }
            return index + 2;
        }
        return left +1 ;       
    }
}