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企业工程师实时在线授课为你传授面试技巧

相关文章
|
1天前
|
算法 搜索推荐 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
5 0
|
2天前
|
算法 程序员 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(中)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
12 0
|
2天前
|
算法 C语言 C++
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(上)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
12 0
|
2天前
|
算法 测试技术
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题(下)
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题
8 0
|
2天前
|
算法
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题(上)
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题
9 0
|
2天前
|
关系型数据库 测试技术 Python
2024年最新【Python 百练成钢】快速上手并查集(2),Python面试简历模板
2024年最新【Python 百练成钢】快速上手并查集(2),Python面试简历模板
|
2天前
|
机器学习/深度学习 编解码 算法
算法工程师面试问题总结 | YOLOv5面试考点原理全解析
本文给大家带来的百面算法工程师是深度学习目标检测YOLOv5面试总结,文章内总结了常见的提问问题,旨在为广大学子模拟出更贴合实际的面试问答场景。在这篇文章中,我们还将介绍一些常见的深度学习目标检测面试问题,并提供参考的回答及其理论基础,以帮助求职者更好地准备面试。通过对这些问题的理解和回答,求职者可以展现出自己的深度学习目标检测领域的专业知识、解决问题的能力以及对实际应用场景的理解。同时,这也是为了帮助求职者更好地应对深度学习目标检测岗位的面试挑战,提升面试的成功率和竞争力。
|
5天前
|
算法 前端开发 Android开发
Android文字基线Baseline算法的使用讲解,Android开发面试题
Android文字基线Baseline算法的使用讲解,Android开发面试题
Android文字基线Baseline算法的使用讲解,Android开发面试题
|
5天前
|
算法 Java API
Groovy脚本基础全攻略,android面试算法题
Groovy脚本基础全攻略,android面试算法题
|
5天前
|
NoSQL 算法 Java
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
【redis源码学习】持久化机制,java程序员面试算法宝典pdf