当前位置: 首页 > article >正文

LeetCode 704.二分查找

LeetCode 704.二分查找

image-20241218220335497

思路🧐:

  在本篇以及之后几篇的博客中,博主将会用二分法进行解答,以此巩固二分题型。二分法一般用于具有二段性的数据中使用。比如该题为有序数组,需要我们查找一个目标值target,分析后发现,这段数据中会出现三种情况,大于target,小于target,等于target,而等于target是我们的目标,于是可以判断出,这个数组是具有二段性的,以target进行分段,由此得出使用二分法。

  我们以下面数组进行举例,首先求出一个中间值,这里我使用left + (right - left) / 2求得中间值,在某些情况下,需要在right - left后面再加上1,否则会导致死循环,具体在之后的篇章中会进行说明。求出中间值nums[mid]=3后,此时target大于3,于是可以得出,[left,mid]之间的所有数据,都不可能含有9,则可以舍去这段区间,得到left = mid + 1,然后再次进行该过程。假如nums[mid] > target,则表示[mid,right]区间可以舍去,则right = mid - 1。当nums[mid] == target时,表示找到了目标值,即可返回。如果left > right,表示整个数组都找完了也没找到目标值,返回-1。

image-20241218221108111

代码🔎:

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

时间复杂度:O(LogN)  空间复杂度:O(1)
image-20241218222607671


http://www.kler.cn/a/448768.html

相关文章:

  • set的使用
  • Linux中的 read() 函数的介绍及使用实例
  • java全栈day20--Web后端实战(Mybatis基础2)
  • mapStateToProps
  • 【NLP 16、实践 ③ 找出特定字符在字符串中的位置】
  • go mod tidy 命令
  • AI的进阶之路:从机器学习到深度学习的演变(三)
  • 前端调试实践
  • Android 蓝牙Bluedroid线程池设计思路介绍
  • 浅谈怎样系统的准备前端面试
  • 【珠江电缆】创新驱动质量升级,树立行业新标杆
  • 题海拾贝:力扣 86.分隔链表
  • 【Redis经典面试题三】Redis有哪些数据类型?
  • 如何在Ubuntu下通过Docker部署PSQL服务器
  • SPringBoot--第二核心--AOP
  • frp内网穿透笔记
  • 工作与学习方向
  • 本地部署webrtc应用怎么把http协议改成https协议?
  • 青少年编程与数学 02-004 Go语言Web编程 10课题、中间件
  • 13 次小生成树
  • vscode怎么设置anaconda python解释器(anaconda解释器、vscode解释器)
  • 【LeetCode: 24. 两两交换链表中的节点 + 链表】
  • MONI后台管理系统-swagger3(springdoc-openapi)集成
  • 齐次矩阵包含平移和旋转
  • CCF-GESP 等级考试 2023年9月认证C++一级真题解析
  • 未来将要被淘汰的编程语言