当前位置：首页 > news >正文

可视化图解算法40：二分查找-I

news 2025/5/17 12:12:42

1. 题目

描述

请实现无重复数字的升序数组的二分查找

给定一个元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

数据范围：0≤len(nums)≤2×105 ，数组中任意值满足val∣≤109

进阶：时间复杂度 O(logn) ，空间复杂度O(1)

示例1

输入：

[-1,0,3,4,6,10,13,14],13

返回值：

6

说明：

13 出现在nums中并且下标为 6

示例2

输入：

[],3

返回值：

-1

说明：

nums为空，返回-1

示例3

输入：

[-1,0,3,4,6,10,13,14],2

返回值：

-1

说明：

2 不存在nums中因此返回 -1

2. 解题思路

先来看一下什么是二分查找？

二分查找是一种高效的搜索算法，适用于有序数组。其核心思想是通过不断缩小搜索范围，将时间复杂度降至 O(log n)。

核心步骤：

初始化指针：设置左指针 left = 0，右指针 right = 数组长度 - 1。

循环查找：当 left <= right 时，重复以下步骤：计算中间索引 mid = left + (right - left) // 2（避免整数溢出）。比较中间元素 arr[mid] 与目标值 target：若相等，返回 mid。若 arr[mid] < target，说明目标在右侧，更新 left = mid + 1。若 arr[mid] > target，说明目标在左侧，更新 right = mid - 1。

未找到：若循环结束未找到，返回 -1。

假如要查找的有序数组、查找元素如下图所示：

定义两个变量left、right，分别指向数组的第0个位置和最后一个位置。这两个变量组成的区间为：[0,n-1]。通过循环缩小数组区间，查找对应的元素，具体操作如下：

关键点

初始区间：通常使用左闭右闭区间 [left, right]，即 left = 0，right = len(nums) - 1。

循环条件：while left <= right，确保所有元素被检查。

中间位置计算：mid = (left + right) // 2 或 mid = left + (right - left) // 2（避免溢出）。

边界更新：

找到目标时，标准二分查找直接返回。

寻找左边界时，中间元素 Arr[mid]>= target 则移动右边界。

寻找右边界时，中间元素 Arr[mid] <= target 则移动左边界。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

Python版本：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372586
Java版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367842
Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364840

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param target int整型* @return int整型*/
func search(nums []int, target int) int {// write code here// 1. 定义变量left := 0right := len(nums) - 1// 2. 通过循环缩小查询区间for left <= right {// 2.1 计算中间位置（数组下标）mid := (left + right) / 2// 2.2 与目标值比较，缩小区间if nums[mid] == target {return mid //中间位置对应的值 等于 目标值，找到，直接返回} else if nums[mid] < target {left = mid + 1 //中间位置对应的值 小于 目标值，则到右侧区间查找（缩小区间：[mid+1,n]）} else {right = mid - 1 //中间位置对应的值 大于 目标值，则到左侧区间查找（缩小区间：[0,mid-1]）}}return -1
}

具体完整代码你可以参考下面视频的详细讲解。

Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372586
Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367842
Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364840