当前位置: 首页> 健康> 科研 > leetcode704二分查找

leetcode704二分查找

时间:2025/7/11 7:39:24来源:https://blog.csdn.net/lxw6666666666/article/details/139768854 浏览次数:0次

本文主要讲解二分查找的要点与细节,按照步骤思考更方便理解

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


示例 1:

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

c++与java代码如下,末尾

具体要点:

1.  这道题要求我们实现二分法,是一个基础的题目,二分法的时间复杂度是 O(log n),所以如果其他题目有时间复杂度的要求,我们也要想到使用二分法

        首先我们要知道二分法的具体操作步骤:

  • 使用二分法必须要求数组有序
  • 进行的是比较操作,将目标值与数组中间元素进行比较
  • 然后决定在数组的哪一半继续搜索。
  • 若找到就返回下标值
  • 若没有找到就返回-1

2. 二分法通常是要使用双指针进行解题,为什么呢?

        主要原因是因为,我们将目标值与数组中间元素进行比较,而中间位置是由左右两端点确定的,区间在不断变化,中间值也是在不断变化的。

        我们就要用两个指针来表示左右端点(或是理解为表示区间),这样就可以进一步表示中间值

        类似双指针题目:左右指针,快慢指针


3. 当我们明确了双指针的含义后,我们就要去考虑每次遍历如何更新双指针

        核心思路:区域不断缩短的前提下,保证target一直处于我们双指针的区域内

        区域如何缩短呢:用中间值去替换我们的左或右指针,这样每次就压缩了一半的区间

        如何保证target在区间内呢(到底要左半边还是右半边呢):

        解决方法:用mid去和left,right对比,保证target在区域内

if (nums[mid] > target) {right = mid - 1;
}
else if (nums[mid] < target) {left = mid + 1;
}
elsereturn mid;

细节问题:

        循环条件到底是left<right,还是left<=right呢?

        对于这类边界条件,我们举个例子就可以搞定,假如left=right时 ,我们就不进入while,不进行任何比较,那么此时就丢掉了一个元素,如果此时元素正好是target那么就恰好丢了结果,返回了-1,而不是正确下标

        (例如nums={5},target=5,只有一个元素,left=0,right=0)


    c++代码如下

#include <vector>
using namespace std;
class Solution {
public:int search(vector<int>& nums, int target) {//使用二分法前提是有序//定义左右指针,分别代表二分的左右顶点int left = 0, right = nums.size() - 1;//二分循环条件left<=rightwhile (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target) {right = mid - 1;}else if (nums[mid] < target) {left = mid + 1;}elsereturn mid;}return -1;}
};

java代码如下:

class Solution {public int search(int[] nums, int target) {if (target < nums[0] || target > nums[nums.length - 1]) return -1;int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) return mid;else if (nums[mid] < target) left = mid + 1;else right = mid - 1;}return -1;}
}

关键字:leetcode704二分查找

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: