leetcode704------二分法查找有序数组中特定的值

目录

一、二分法的基本概念 

二、二分法的基本步骤

三、迭代二分法查找有序数组中的特定值题目

3.1 题目介绍 

3.2 求解思路

3.2.1 情况一：左闭右闭[left, right]

3.2.2 情况二：左闭右开[left, right) 

四、二分法的时间复杂度与空间复杂度

4.1 时间复杂度

4.2 空间复杂度

一、二分法的基本概念 

二分法，也称为折半查找，是一种在有序数组中高效查找特定元素的搜索算法。它的基本思想是通过不断地将搜索区间减半来快速定位目标元素。具体实现是：首先确定搜索区间的中间元素，如果中间元素等于目标值，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。

二、二分法的基本步骤

1. 定义查找的范围：初始时设定查找区间的左右边界，通常用两个指针left和right。
2. 计算中间位置：mid = (left + right) // 2，即区间的中间索引。
3. 比较中间元素：
   • 如果array[mid] == target，则找到目标，返回索引。
   • 如果array[mid] < target，则目标在右半部分，更新left = mid + 1。
   • 如果array[mid] > target，则目标在左半部分，更新right = mid - 1。
4. 重复以上步骤，直到找到目标或者区间为空（left > right）。

三、迭代二分法查找有序数组中的特定值题目

3.1 题目介绍 

题目来源：leetcode第704道题目

题目链接：https://leetcode.cn/problems/binary-search/description/

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

示例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]之间。

3.2 求解思路

这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。当然也可以左开右闭(left, right]，但是这种不推荐。

3.2.1 情况一：左闭右闭[left, right]

第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

• while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=。
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1。

例如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：

伪代码

// 情况1：查找区间在[left,right]
二分法查找(target) // target 表示要查找的目标值
{
   // 一些变量的定义   
   left=0; // 左边界从0开始
   right=nums.size-1; // 右边界为数组的长度-1，nums表示数组

   
   // 开始二分法
   while(left<=right) // 查找区间在[left,right]，因此为<=
   {
      middle = (left+right)/2; // 中间索引
      if(nums[middle]>target) // 条件成立时，说明target在左子区间，此时更新right即可
      {
          right = middle-1; // 为什么是middle-1而不是middle？原因：在if判断语句中条件为nums[middle]>target，已经确保nums[middle]不会等于target，也就是说下标索引为middle的值必然不符合，若为right = middle，那么在下一次while循环的时候遍历的区间即为[left=0,right=middle]，也就是说，程序把本该不属于自己搜索区间的值放在了搜索区间进行搜索，这造成了矛盾。
     
      elif(nums[middle]<target) // 条件成立时，说明target在右子区间，此时更新left即可
      {
         left=middle+1;
      }
      else // nums[middle] == target
      {
          return middle; // 返回中间索引
      } 
   }
return -1; //返回-1，没有找到目标值
   
}

 正式代码【C++版本】

#include<iostream>
#include<vector>
// 二分法查找顺序数组中指定元素
int binary_seperate(std::vector<int> nums, int target){
    // 定义左边界以及右边界
    int left = 0; // 左边界
    int right = nums.size() - 1; // 右边界
    while(left<=right){
        int middle = (left+right)/2;
        if(nums[middle]>target){ // 条件成立，说明target在左子区间，此时需更新right边界
            right = middle - 1; // 这里right不能等于middle，伪代码中有解释
        }
        else if(nums[middle]<target){ // 条件成立，说明target在右子区间，此时需更新 left 边界
            left = middle + 1;
        }
        else{ // nums[middle]==target，找到目标值
            return middle; // 返回目标值所在下标
        }
    }
    return -1; // 如果没有找到，那就返回 -1
}

int main() {
    std::vector<int> nums1{1,2,3,4,7,9,10}; // 定义一个数组
    int found_target=2; // 要查询的值
    int erfen_found = binary_seperate(nums1, found_target);
    std::cout<< "要找的目标值为:"<< found_target <<",其索引所在位置为:"<<erfen_found << std::endl;
    return 0;

}

3.2.2 情况二：左闭右开[left, right) 

伪代码

// 情况2：查找区间在[left,right)
二分法查找(nums,target) // nums表示待查询的数组，target 表示要查找的目标值
{
   // 一些变量的定义   
   left=0; // 左边界从0开始
   right=nums.size; // 此时右边界为数组的长度，这是因为查找区间在[left,right)，right取不到，因此要多加一个，即把“-1”去掉

   
   // 开始二分法
   while(left<right) // 查找区间在[left,right)，因此为<
   {
      middle = (left+right)/2; // 中间索引
      if(nums[middle]>target) // 条件成立时，说明target在左子区间，此时更新right即可
      {
          right = middle; // 为什么是middle？原因：如果right = middle-1，那么下一次搜索空间是[left=0,right=middle-1)，这样就会少搜索了nums[middle-1]这个值。
     
      elif(nums[middle]<target) // 条件成立时，说明target在右子区间，此时更新left即可
      {
         left=middle+1;
      }
      else // nums[middle] == target
      {
          return middle; // 返回中间索引
      } 
   }
return -1; //返回-1，没有找到目标值
   
}

正式代码【C++版本】 

// 情况2： 查找范围为[left,right)，注意，此时不包含right边界值
int binary_seperate(std::vector<int> nums, int target){
    int left = 0;
    int right = nums.size();

    while(left<right){
        int middle = (left+right)/2;
        if(nums[middle]>target){
            right = middle;
        }
        else if(nums[middle]<target){
            left = middle + 1;
        }
        else{ // nums[middle]==target
            return middle; // 找到，返回下标索引
        }
    } 
    return -1; // 没找到，返回-1
}


int main() {
    std::vector<int> nums1{1,2,3,4,7,9,10}; // 定义一个数组
    int found_target=2; // 要查询的值
    int erfen_found = binary_seperate(nums1, found_target);
    std::cout<< "要找的目标值为:"<< found_target <<",其索引所在位置为:"<<erfen_found << std::endl;
    return 0;

}

四、二分法的时间复杂度与空间复杂度

4.1 时间复杂度

• 时间复杂度为O(log n)，因为每次查找都会将查找区间缩小一半。

解析： 

二分法通过每次将搜索区间分成两半来查找目标元素。假设初始时数组有 n 个元素，二分法每次都会检查中间的元素，并将搜索范围缩小到剩下的一半。这样，随着每一步的进行，搜索区间的大小减少一半，直到搜索区间大小为1。

具体步骤：

1. 第一次迭代：在 n 个元素中找到中间元素，将搜索区间缩小为 n / 2。
2. 第二次迭代：再将剩余的 n / 2 个元素分为两半，缩小到 n / 4。
3. 第三次迭代：继续缩小到 n / 8，以此类推。
4. 经过 k 次迭代后，剩余的搜索区间大小为：n/(2^k)​
5. 当剩余的搜索区间只有一个元素时，即：n/(2^k)​=1
6. 解这个方程，得到：k=log2​n

所以，经过大约 log₂(n) 次迭代，算法将停止，并找到目标元素或确认目标元素不存在。

关于时间复杂度为什么是这个值，请观看视频：https://www.bilibili.com/video/BV1aw411A7uL?spm_id_from=333.788.videopod.sections&vd_source=fb7bfda367c76676e2483b9b60485e57

4.2 空间复杂度

空间复杂度为 O(1)。

• 只使用了常量额外空间

  • 代码中只使用了几个整数变量：left、right 和 middle。
  • 这些变量的存储空间 不会随着输入数组的大小变化，始终是常量级别的空间需求。

• 不依赖额外的数据结构

  • 代码没有使用递归，也没有额外分配数组、列表或其他数据结构。
  • 所有计算都在原始数组 nums 上进行，没有额外存储需求。