首页 > 试题广场 >

二分查找

[编程题]二分查找
  • 热度指数：155398 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
请实现有重复数字的升序数组的二分查找。
输出在数组中第一个大于等于查找值的位置（下标从1开始算起），如果数组中不存在这样的数(指不存在大于等于查找值的数)，则输出数组长度加一。
示例1

输入

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

输出

3

说明

输出位置从1开始计算
示例2

输入

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

输出

5

说明

虽然数组中没有4，但 5 ≥ 4 ，所以返回5对应的位置，刚好也是5。
算法知识视频讲解
添加回答
Python
牛客560265042号大猫头像 牛客560265042号大猫
def search(nums,target):
    if target not in nums:
        return len(nums)+1
    left=0
    right=len(nums)-1
    while left<right:
        mid=(right+left)//2
        if nums[mid]>=target:
            right=mid
        else:
            left=mid+1
    return left+1
list=[3,4,4,5,7]
t=6
res=search(list,t)
print(res)
发表于 2023-03-06 15:49:46 回复(0)
Python
Harvey_2015头像 Harvey_2015
编程小白： 
#
# 二分查找
# @param n int整型 数组长度
# @param v int整型 查找值
# @param a int整型一维数组 有序数组
# @return int整型
#
class Solution:
    def upper_bound_(self , n , v , a ):
        # write code here
        l = n+1
        for i in range(n):
            if a[i] >= v:
                l = i+1
                break
        return l
发表于 2021-01-03 16:36:58 回复(0)
Python
叶123456头像 叶123456 
import math
class Solution:
    def upper_bound_(self , n , v , a ):
        heads=0
        tail=n-1
        nums=math.ceil(n/2)
        flag=0
        while heads<=nums and tail>=nums:
            if a[heads]>=v:
                flag=heads+1
                return flag
            if a[tail]>=v:
                flag=tail+1
            heads+=1
            tail-=1
        if flag>0:
            return flag
        else:
            return n+1

发表于 2020-12-09 16:29:21 回复(0)
Python
zawabest头像 zawabest 
# 二分查找
# @param n int整型 数组长度
# @param v int整型 查找值
# @param a int整型一维数组 有序数组
# @return int整型
#
class Solution:
    def upper_bound_(self , n , v , a ):
        # write code here
        l = 0
        r = n - 1
        while l <= r:
            m = (l + r) >> 1
            if a[m] >= v:
                r = m - 1
            else:
                l = m + 1
        return r + 2

发表于 2020-11-26 19:54:04 回复(0)
Python
牛客798621139号头像 牛客798621139号 
#
# 二分查找
# @param n int整型 数组长度
# @param v int整型 查找值
# @param a int整型一维数组 有序数组
# @return int整型
#
class Solution:
    def upper_bound_(self , n , v , a ):
        # write code here
        if n<1: return 1
        if a[-1] < v: return n+1
        p = (n-1) // 2
        if v <= a[p]:
            return self.upper_bound_(p, v, a[:p])
        else:
            return p + self.upper_bound_(n-p, v, a[p:])
没看到有递归做的，分享一个
发表于 2020-10-13 14:31:56 回复(1)
Python
千寻者头像 千寻者 
#
# 二分查找
# @param n int整型 数组长度
# @param v int整型 查找值
# @param a int整型一维数组 有序数组
# @return int整型
#
class Solution:
    def upper_bound_(self , n , v , a ):
        # write code here
        if a[n-1]<v:
            return n+1
        def bi_find():
            left,right=0,n-1
            while left<right:
                mid = (left+right)//2
                if a[mid]==v:
                    tmp = mid-1
                    while tmp>=left and a[tmp]==a[tmp+1]:
                        tmp-=1
                    return tmp+2
                elif a[mid]>v:
                    right=mid
                else:
                    left=mid+1
            return right+1
        return bi_find()

发表于 2020-10-07 14:21:22 回复(1)
Python
小菜鸡海贼头像 小菜鸡海贼
根据二分法的思想将原数组“裁剪”至只剩下一个元素，然后判断该元素是否满足大于等于目标元素，最后根据判断结果进行输出
发表于 2020-10-05 17:23:55 回复(0)
Python
qyzhizi头像 qyzhizi 
class Solution:
    def upper_bound_(self , n , v , a ):
        # write code here
        lo = 0
        hi = len(a)
        while lo < hi:
            mi = (lo + hi) // 2
            if a[mi] < v:
                lo = lo+1 # 这里写错了， 应该是 lo = mi + 1
            else:
                hi = mi
        return lo+1

清华邓公里面有这个二分查找思路：
区间[lo,hi) 表示待定区域，[0,lo),表示绝对小于value的区域， [mi,hi)，表示大于等于value的区域
最后得到的lo 的语意刚好满足，只不过本题给出的答案要加一，表示的不是秩，而是位置。
编辑于 2021-03-04 00:15:17 回复(4)
提交观点

问题信息

二分
上传者：牛客332641号
难度：
9条回答 14647浏览

热门推荐

通过挑战的用户

相关试题

二分查找

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号