知识卡片
二分查找每次排除半个有序区间
二分查找要求数据按与compare一致的规则有序,取当前范围中点比较:中点小于目标则排除它及左半,大于则排除它及右半,相等返回。每次排除中点本身,才能让剩余候选严格减少。
闭区间实现从left=0、right=n−1开始,更新left=middle+1或right=middle−1,left>right时为空而失败;左右相等时仍有一个候选,不能像正文那样一概称重合即未找到。
O(log n)指候选比较层数,并依赖便宜访问中点和受控比较成本;本例用连续数组实现,不代表抽象算法逻辑只能用于物理连续内存。链表访问中点昂贵时,总成本会不同。
223/02978–02980 while(left<=right),命中return middle,退出return−1。02977在[10,14,21,38,45,47,53,81,87,99]找47,依次比较下标4的45、7的81、5的47,返回5。没有命中时是边界交错而非必须重合。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
中间的那个元素。如果此元素比要查找的元素大,就接着在较小的一个半区进行查找;反之,如果此元素比要查找的元素小,就在较大的一个半区进行查找。在每个更小的数据集中重复这个查找过程,直到找到要查找的元素或者数据集不能再分割。 二分查找能够应用于任何类型的数据,只要能将这些元素按某种规则进行排序。这是一个简
- · 查看原书依据
left和right控制的一个循环来查找元素(其中left和right是正在进行查找的数据集的两个边界值)。首先,将left和right分别设置为0和size-1。在循环的每次迭代过程中,将middle设置为left和right之间区域的中间值。如果处于middle的元素比目标值小,将左索引值移动到
参考来源
- 位置:《算法精解:C语言描述》第12章《二分查找的描述》(spine1353;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1319.html;u221-ch12-018)。
- 结论依据:221全部猜数/有序/动态数据段与223/02978–02980完整闭区间实现实读,保留循环条件和非连续表示的访问成本边界。
- 原始内容:中间的那个元素。如果此元素比要查找的元素大,就接着在较小的一个半区进行查找;反之,如果此元素比要查找的元素小,就在较大的一个半区进行查找。在每个更小的数据集中重复这个查找过程,直到找到要查找的元素或者数据集不能再分割。 二分查找能够应用于任何类型的数据,只要能将这些元素按某种规则进行排序。这是一个简
- 位置:《算法精解:C语言描述》第12章《二分查找的实现与分析》(spine1355;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1321.html;u223-ch12-018)。
- 结论依据:223/02978–02980 while(left<=right),命中return middle,退出return−1。02977在[10,14,21,38,45,47,53,81,87,99]找47,依次比较下标4的45、7的81、5的47,返回5。没有命中时是边界交错而非必须重合。
- 原始内容:left和right控制的一个循环来查找元素(其中left和right是正在进行查找的数据集的两个边界值)。首先,将left和right分别设置为0和size-1。在循环的每次迭代过程中,将middle设置为left和right之间区域的中间值。如果处于middle的元素比目标值小,将左索引值移动到