牛客题霸NC105题解

二分查找

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

二分查找

牛客题霸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;
    }
}
全部评论

相关推荐

仁者伍敌:牛子这些人还会点一个自动回复,boss都不带回复的
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
07-11 10:56
门头沟学院 Java
码客明:大胆的说自己能实习6个月就行
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务