牛客题霸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;
    }
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-15 17:07
途虎_JAVA
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议