Binary Search

Idea

Binary Search halves the search range each step—requires a sorted list.

折半查找法（Binary Search）演示

1357911

下一步

When to use

• Sorted linear list (array or list)
• Large data, frequent queries

Algorithm

1. Range $[low, high]$
2. $mid = \lfloor (low + high) / 2 \rfloor$
3. If $A[mid] = x$, success
4. If $A[mid] < x$, search right half
5. If $A[mid] > x$, search left half
6. Stop when $low > high$

Pseudo-code:

low = 0, high = n-1
while low <= high:
    mid = (low + high) // 2
    if A[mid] == x:
        return mid
    elif A[mid] < x:
        low = mid + 1
    else:
        high = mid - 1
return -1

Complexity

• Best: $O(1)$
• Worst/avg: $O(\log_2 n)$

Exercises

Exercise 1

For sorted $A = [1, 3, 5, 7, 9, 11]$, find $7$.

参考答案

思路：每次折半。

步骤：

1. $low=0, high=5, mid=2, A[2]=5<7$
2. $low=3, high=5, mid=4, A[4]=9>7$
3. $low=3, high=3, mid=3, A[3]=7$

答案：下标 $3$。

Exercise 2

适用条件与时间复杂度？

参考答案

思路：前提与效率。

步骤：

1. 适用于有序表
2. 时间复杂度 $O(\log_2 n)$

答案：有序表，$O(\log_2 n)$。

Past exam

2017·408

折半查找过程与效率？

参考答案

思路：描述流程与比较次数。

步骤：

1. 每次比中间，区间减半
2. 最多比较 $\log_2 n$ 次

答案：折半，$O(\log_2 n)$。

PreviousBlock SearchBlock search basics, algorithm flow, complexity, and practice. NextHash Table SearchHash-table searching: hash functions, collision handling, complexity, and practice.