Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"洛谷-P1024\":[\"一元三次方程求解\",82525,\"NOIP2001 提高组\"],\"洛谷-P1258\":[\"小车问题\",12214,null],\"洛谷-P8647\":[\"分巧克力\",11915,\"蓝桥杯 2017 省 AB\"],\"洛谷-P2249\":[\"查找\",110778,\"深基13.例1\"],\"洛谷-P7713\":[\"打分\",2302,\"EZEC-10\"],\"洛谷-P1314\":[\"聪明的质监员\",24228,\"NOIP2011 提高组\"],\"洛谷-P2678\":[\"跳石头\",82764,\"NOIP2015 提高组\"],\"洛谷-P1083\":[\"借教室\",37742,\"NOIP2012 提高组\"],\"洛谷-P1902\":[\"刺杀大使\",9613,null],\"洛谷-P1824\":[\"进击的奶牛\",46609,null],\"洛谷-P4343\":[\"自动刷题机\",5977,\"SHOI2015\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"Exile_code","updateTime":1706702148000,"title":"基础算法入门(二分)","dislikeCnt":0,"content":"# 基础算法入门(二分)\n\n## 二分查找算法思想\n\n二分查找是一种高效的搜索算法,它基于有序数组的单调性,通过反复将查找范围缩小一半的方式找到目标值。这种算法的时间复杂度为O(log n),相比于线性搜索,它在大规模数据中表现出更高的效率。\n\n## 算法步骤\n\n1. **初始化**:确定搜索的初始范围,通常是整个数组。\n2. **迭代或递归**:在每一步中,计算中间元素的索引,将目标值与中间元素进行比较。\n - 如果目标值等于中间元素,搜索完成,返回中间元素的索引。\n - 如果目标值小于中间元素,说明目标值在左半部分,更新搜索范围为左半部分。\n - 如果目标值大于中间元素,说明目标值在右半部分,更新搜索范围为右半部分。\n3. **终止条件**:当搜索范围缩小到空集时,表示未找到目标值。\n\n## 代码示例\n\n```\nint binarySearch(vector\u003cint\u003e\u0026 nums, int target) \n{\n int left \u003d 0, right \u003d nums.size() - 1;\n\n while (left \u003c\u003d right) \n {\n int mid \u003d left + (right - left) / 2;\n\n if (nums[mid] \u003d\u003d target)\n return mid; // 找到目标值,返回索引\n else if (nums[mid] \u003c target)\n left \u003d mid + 1; // 目标值在右半部分\n else\n right \u003d mid - 1; // 目标值在左半部分\n }\n }\n\n return -1; // 目标值不存在\n}\n```\n\n## 适用场景\n\n二分查找适用于有序数组或有序列表,它的高效性使得在大规模数据中查找目标值时成为首选算法。常见的应用包括搜索特定元素、查找边界值、在有序数组中插入元素等。\n\n## 注意事项\n\n1. **数组必须有序**:二分查找要求目标数组是有序的,否则无法保证查找的正确性。\n2. **适用于静态数据**:如果数组内容频繁变动,不断插入或删除元素,二分查找可能不是最佳选择,因为每次变动都需要重新排序。\n3. **变体问题**:在某些情况下,需要考虑二分查找的变体问题,例如查找第一个大于等于目标值的元素索引、查找最后一个小于等于目标值的元素索引等。\n\n## 学习链接\n\n[手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1fA4y1o715/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n## 练习题目\n\n[problem:洛谷-P8647],[problem:洛谷-P7713],[problem:洛谷-P2249],[problem:洛谷-P1258],[problem:洛谷-P1824],[problem:洛谷-P1024],[problem:洛谷-P2678],[problem:洛谷-P1902],[problem:洛谷-P1314],[problem:洛谷-P1083],[problem:洛谷-P4343]","threadId":181142,"likeCnt":1,"createTime":1706702148000,"isWorkbook":true,"viewCnt":371,"openness":2,"fav":false,"id":4536,"trustable":false}