金乌智能--数据抓取、数据采集、爬虫

让每个人都轻松拥抱爬虫技术,拥有大数据技术!

二分查找

二分查找、面试、算法


题目描述

请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。
示例1

输入

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

返回值

3

说明

输出位置从1开始计算 

解题思路:难点在于查找的值是相同的,就可以按着大于的思路往下找,直到找不到大于等于的

#
# 二分查找
# @param n int整型 数组长度
# @param v int整型 查找值
# @param a int整型一维数组 有序数组
# @return int整型
#
class Solution:
    def upper_bound_(self , n , v , a ):
        # write code here
        if v > a[n-1]:
            return n + 1
        if v < a[0]:
            return 1
        l, r = 0, n-1
        while l <= r:
            mid = (l + r)//2
            if  v <= a[mid]:
                r = mid -1
            else:
                l = mid + 1
        return l + 1

博文最后更新时间:


评论

  • 暂无评论

发表评论

博客统计

访问量:99603

博文总数:112 评论总数:0

原创112 翻译0 转载0