“Binary search”的版本间的差异
跳到导航
跳到搜索
（→变化） |
（→变化） |
||
| 第23行： | 第23行： | ||
<code>mid</code> 赋值为 <code>floor((left + right) / 2)</code> 时，需要用 <code>left = mid + 1</code> 和 <code>right = mid</code>，循环判断为 <code>left < right</code> <ref>https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md</ref> | <code>mid</code> 赋值为 <code>floor((left + right) / 2)</code> 时，需要用 <code>left = mid + 1</code> 和 <code>right = mid</code>，循环判断为 <code>left < right</code> <ref>https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md</ref> | ||
| − | === | + | === 找第一次出现的下标（bisect_left）=== |
| − | 如需找到元素第一次出现的下标（[https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ Leetcode 34. Find First and Last Position of Element in Sorted Array]），可将 <code>mid_calc</code> 等于和大于的情况合并，并给新的 high 赋值时不 <code> | + | 如需找到元素第一次出现的下标（[https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ Leetcode 34. Find First and Last Position of Element in Sorted Array]），可将 <code>mid_calc</code> 等于和大于的情况合并，并给新的 high 赋值时不 <code>- 1</code>。 |
| + | Python 示例：<ref>https://github.com/python/cpython/blob/3.13/Lib/bisect.py</ref> | ||
| + | <syntaxhighlight lang=python> | ||
| + | def bisect_left(arr, x): | ||
| + | lo = 0 | ||
| + | hi = len(arr) | ||
| + | while lo < hi: | ||
| + | mid = (lo + hi) // 2 | ||
| + | if arr[mid] < x: | ||
| + | lo = mid + 1 | ||
| + | else: | ||
| + | hi = mid | ||
| + | return lo | ||
| + | </syntaxhighlight> | ||
| + | |||
| + | <!-- | ||
C++ 示例：<ref>https://github.com/changgyhub/leetcode_101</ref> | C++ 示例：<ref>https://github.com/changgyhub/leetcode_101</ref> | ||
<syntaxhighlight lang=cpp> | <syntaxhighlight lang=cpp> | ||
| 第43行： | 第58行： | ||
return low; | return low; | ||
} | } | ||
| + | </syntaxhighlight> | ||
| + | --> | ||
| + | |||
| + | === 找最后一次出现的下标+1（bisect_right）=== | ||
| + | |||
| + | Python 示例 | ||
| + | <syntaxhighlight lang=python> | ||
| + | def bisect_right(arr, x): | ||
| + | lo = 0 | ||
| + | hi = len(arr) | ||
| + | while lo < hi: | ||
| + | mid = (lo + hi) // 2 | ||
| + | if arr[mid] > x: | ||
| + | hi = mid | ||
| + | else: | ||
| + | lo = mid + 1 | ||
| + | return lo | ||
</syntaxhighlight> | </syntaxhighlight> | ||
2025年2月20日 (四) 09:14的最新版本
二分法。
一般 pattern
low = 0
high = n
while low <= high:
mid = (low + high) // 2
mid_calc = f(mid)
if mid_calc == target:
return g(mid)
elif mid_calc < target:
low = mid + 1
else:
high = mid - 1
return default_retval
注意 low <= high, low = mid + 1 和 high = mid - 1。while 循环结束后 low 的值是新元素的插入位置。
变化
mid 赋值为 floor((left + right) / 2) 时，需要用 left = mid + 1 和 right = mid，循环判断为 left < right [1]
找第一次出现的下标（bisect_left）
如需找到元素第一次出现的下标（Leetcode 34. Find First and Last Position of Element in Sorted Array），可将 mid_calc 等于和大于的情况合并，并给新的 high 赋值时不 - 1。
Python 示例：[2]
def bisect_left(arr, x):
lo = 0
hi = len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
找最后一次出现的下标+1（bisect_right）
Python 示例
def bisect_right(arr, x):
lo = 0
hi = len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] > x:
hi = mid
else:
lo = mid + 1
return lo