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

【算法题攻略】二分查找

news 2026/7/17 6:45:51

文章目录

一、习题解析
- 1. 二分查找（模板题，详述二分查找的解题过程）
- 2. 在排序数组中查找元素的第一个和最后一个位置
- 3. 寻找峰值
- 4. 搜索旋转排序数组中的最小值
二、练习题
- 1. 点名

一、习题解析

1. 二分查找（模板题，详述二分查找的解题过程）

题目链接: 704. 二分查找

题目描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

代码实现：

classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;inttar_index=-1;while(left<=right){intmid=(left+right)/2;if(nums[mid]<target){left=mid+1;}elseif(nums[mid]>target){right=mid-1;}else{tar_index=mid;break;}}returntar_index;}};

2. 在排序数组中查找元素的第一个和最后一个位置

题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置

题目描述：

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

示例 3:
输入: nums = [], target = 0
输出: [-1,-1]

提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9

代码实现：

classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){vector<int>vec={-1,-1};if(nums.size()==0||target>nums.back()||target<nums[0]){returnvec;}// 1. 二分法寻找 目标值在数组的开始位置intleft=0,right=nums.size()-1;while(left<right){intmid=(left+right)/2;if(nums[mid]<target)left=mid+1;elseif(nums[mid]>=target)right=mid;}if(nums[left]==target)vec[0]=left;// 2. 二分法寻找 目标值在数组的结束位置left=0,right=nums.size()-1;while(left<right){intmid=(left+right+1)/2;if(nums[mid]<=target)left=mid;elseif(nums[mid]>target)right=mid-1;}if(nums[left]==target)vec[1]=left;returnvec;}};

3. 寻找峰值

题目链接: 162. 寻找峰值

题目描述：

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释：3 是峰值元素，你的函数应该返回其索引 2

示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5，其峰值元素为 6

提示：
1 <= nums.length <= 1000
-2^31 <= nums[ i ] <= 2^31 - 1
对于所有有效的 i 都有 nums[ i ] != nums[ i + 1 ]

代码实现：

classSolution{public:intfindPeakElement(vector<int>&nums){if(nums.size()==1)return0;intleft=0,right=nums.size()-1;while(left<right){intmid=(left+right)/2;if(nums[mid]<nums[mid+1])left=mid+1;elseif(nums[mid]>nums[mid+1])right=mid;}returnleft;}};

4. 搜索旋转排序数组中的最小值

题目链接: 153. 寻找旋转排序数组中的最小值

题目描述：

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

（1）若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
（2）若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1:
输入: nums = [3,4,5,1,2]
输出: 1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2:
输入: nums = [4,5,6,7,0,1,2]
输出: 0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3:
输入: nums = [11,13,15,17]
输出: 11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

代码实现：

classSolution{public:intfindMin(vector<int>&nums){if(nums.size()==1)returnnums[0];if(nums[0]<nums[1]&&nums[0]<nums.back())returnnums[0];inttarget=nums[nums.size()-1];intleft=0,right=nums.size()-1;while(left<right){intmid=(left+right)/2;if(nums[mid]>target)left=mid+1;elseif(nums[mid]<=target)right=mid;}returnnums[left];}};