算法训练营第一天| 704. 二分查找

张开发
• 2026/4/14 2:01:18 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

算法训练营第一天| 704. 二分查找
一、今日学习内容今日任务先把 704写熟练要熟悉根据左闭右开,左闭右闭两种区间规则写出来的二分法。题目建议了解一下数组基础以及数组的内存空间地址数组也没那么简单。题目链接https://leetcode.cn/problems/binary-search/视频讲解https://www.bilibili.com/video/BV1fA4y1o715二、自己看到题目的第一想法看到有序数组、O(log n)时间复杂度第一反应就是二分查找。大概思路每次取中间比较小了往右找大了往左找。边界条件容易写错有时候会死循环有时候漏掉元素这次要按两种区间规则来写。三、实现过程中遇到哪些困难1、边界处理。一开始写左闭右闭版本while里用了结果当leftright时直接退出了漏掉了最后一个元素。后来改成就好了。2、左闭右开版本不习惯right初始是nums.size()不是size()-1while条件用更新right时直接等于mid不用减1。刚开始总想写成mid-1因为习惯闭区间了多写几遍才记住。3、计算mid时要用left (right - left) / 2防止溢出。四、代码是怎么实现的1、左闭右闭版本 [left, right]思路初始化时left和right分别指向数组的首尾元素即left 0right nums.size() - 1。循环条件使用是为了确保当left right时区间内的最后一个元素也能被检查到。若nums[mid] target则目标值位于左半部分此时将right更新为mid - 1以排除已检查的mid位置若nums[mid] target则目标值在右半部分将left更新为mid 1若相等则直接返回mid索引。2、左闭右开版本 [left, right)思路左指针指向区间首元素右指针指向区间尾后元素即区间范围为[left, right)。因此初始时left0rightnums.size()。循环条件使用left right因为当left right时区间[left, right)已为空无需继续查找。若nums[mid] target说明目标值在左半区间此时更新右边界为 mid由于右边界是开区间mid 本身不包含在内故无需减 1。若nums[mid] target说明目标值在右半区间此时更新左边界为mid1因 mid 已比较过应从下一位置开始查找。五、今日收获心得二分查找的关键是区间定义要明确然后全程保持一致。循环不变量这个概念很有用想清楚区间定义边界怎么处理就清楚了。边界点容易掌握不好要多练习。刷题不能光看得自己手敲调试一遍比看十遍管用。

更多文章