LintCode 题解丨大厂算法面试模板:二分查找

简介: LintCode 题解丨大厂算法面试模板:二分查找

给定一个排序的整数数组(升序)和一个要查找的整数​target​,用​O(logn)​的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回​-1​。

在线评测地址:

LintCode 领扣

样例 1:

输入:[1,4,4,5,7,7,8,9,9,10],1
输出: 0

样例解释:
第一次出现在第0个位置。
样例 2:

输入: [1, 2, 3, 3, 4, 5, 10],3
输出: 2

样例解释:
第一次出现在第2个位置
样例 3:

输入: [1, 2, 3, 3, 4, 5, 10],6
输出: -1

样例解释:
没有出现过6, 返回-1
解题思路

题目提到,给定的数组已经排序,若从小到大遍历数组查找target,则时间复杂度为O(n)O(n),n为数组长度。需要用一个O(logn)O(logn)的时间复杂度去完成本题,那么需要用到二分查找。

二分查找常用于查找有序数组中目标数target的位置,用​left​和​right​记录target所在的区间端点,每次将区间的中间位置值和target作比较,然后移动区间端点。

算法流程

将区间赋值为整个数组区间(left = 0, right = n - 1),取中间位置mid
若​a[mid]​ < target,则将区间缩小到原区间的右区间(left = mid + 1)
若​a[mid]​ >= target,则将区间缩小至原区间的左区间(right = mid)
若left >= right 时,若​a[right]​ = target则返回right, 否则返回-1
复杂度分析

时间复杂度:O(logn)
每次查找都将区间缩小至原来长度的一半,可见查找的最多次数为logn
空间复杂度:O(1)
查找不需要开辟新的非常数级空间,只需在原数组基础上进行查找即可
代码

public class Solution {

/**
 * @param nums: The integer array.
 * @param target: Target to find.
 * @return: The first position of target. Position starts from 0.
 */
public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int mid;

    while (left < right) {
        //得到中间位置
        mid = (right + left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    if (nums[right] == target) {
        return right;
    }

    return -1;
}

}
更多题解参考:

九章算法 - 帮助更多中国人找到好工作,硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

相关文章
|
4月前
|
算法
面试场景题:如何设计一个抢红包随机算法
本文详细解析了抢红包随机算法的设计与实现,涵盖三种解法:随机分配法、二倍均值法和线段切割法。随机分配法通过逐次随机分配金额确保总额不变,但易导致两极分化;二倍均值法优化了金额分布,使每次抢到的金额更均衡;线段切割法则将总金额视为线段,通过随机切割点生成子金额,手气最佳金额可能更高。代码示例清晰,结果对比直观,为面试中类似算法题提供了全面思路。
976 16
|
5月前
|
算法 Java 索引
算法系列之搜素算法-二分查找
二分查找是一种在`有序`数组中查找特定元素的算法。它的基本思想是通过将数组分成两半,逐步缩小查找范围,直到找到目标元素或确定目标元素不存在。
64 9
算法系列之搜素算法-二分查找
|
4月前
|
算法 安全 搜索推荐
套用算法模板备案审核问题增多的原因及解决建议
随着算法备案要求的完善,企业常因使用网上廉价模板而遭遇审核通过率低、问题增多的困境。本文分析了审核不通过的原因,包括模板缺乏针对性、审核标准严格、审核人员主观差异及企业准备不足等,并提出建议:深入了解备案要求、准备详尽材料、避免通用模板、寻求专业帮助。备案后还需持续合规管理,确保算法服务安全运行。
|
6月前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
195 16
|
7月前
|
算法 索引
【算法】——二分查找合集
二分查找基础模版和进阶模版,查找元素位置,搜索插入位置,x的平方根,山脉数组的峰顶索引,寻找峰值,点名
|
9月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
9月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
9月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
9月前
|
算法 C# 索引
C#二分查找算法
C#二分查找算法
|
9月前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法
103 0

热门文章

最新文章