数据结构与算法

1. 二分查找

• 想象你在玩一个猜数字的游戏，数字范围是1到100。如果每次都猜中间的数字，然后根据提示（比如“猜大了”或“猜小了”）来调整你的猜测范围，那么很快就可以找到正确的数字。
• 二分查找就是这样的原理，每次都猜中间的数字，然后根据结果来缩小查找范围。这样的查找方法非常高效，因为每次都可以排除一半的可能性。

二分查找是一种在有序列表中查找特定元素的算法。其基本思想是，通过与中间元素比较，将待查找的范围缩小一半，从而达到快速查找的目的。

为什么叫“二分”查找？

因为每次我们都把列表分成两部分，只在其中一个部分里继续查找，这样查找范围每次都减少一半。

原理：

1. 先找到有序列表的中间元素。
2. 比较中间元素与要查找的元素。
3. 如果它们相等，就返回中间元素的位置。
4. 如果要查找的元素比中间元素大，那么我们就在列表的右半部分（中间元素之后的部分）继续查找。
5. 如果要查找的元素比中间元素小，那么我们就在列表的左半部分（中间元素之前的部分）继续查找。
6. 重复上述过程，直到找到元素或者查找范围为空。

举例：

假设我们有一个有序的数字列表：[1, 3, 4, 5, 7, 8, 9, 10, 12, 14, 15]，我们想要找数字8。

1. 首先，我们找到中间的数字，它是8。
2. 8正好是我们要找的数字，所以我们找到了并返回它的位置。

如果我们要找的是数字4：

1. 我们首先找到中间的数字，它是8。
2. 4比8小，所以我们只在左半部分[1, 3, 4, 5, 7]继续查找。
3. 在这个新的子列表中，中间的数字是4。
4. 4正好是我们要找的数字，所以我们找到了并返回它的位置。

python举例

def binary_search(arr, x):
    """
    Perform binary search on a sorted list to find the position of element x.
    
    :param arr: A sorted list.
    :param x: The element to search for.
    :return: The position of x in arr, or -1 if x is not found.
    """
    
    # Define initial low and high pointers
    low, high = 0, len(arr) - 1
    
    # While the low pointer does not surpass the high pointer
    while low <= high:
        
        # Calculate the middle index
        mid = (low + high) // 2
        
        # If the element at the middle index is the one we're looking for
        if arr[mid] == x:
            return mid
        
        # If the element at the middle index is greater than x, we look in the left half
        elif arr[mid] > x:
            high = mid - 1
        
        # If the element at the middle index is less than x, we look in the right half
        else:
            low = mid + 1
    
    # If we've exhausted the search space and haven't found x, return -1
    return -1

# Example
arr_example = [1, 3, 4, 5, 7, 8, 9, 10, 12, 14, 15]
x1 = 8
x2 = 4
position1 = binary_search(arr_example, x1)
position2 = binary_search(arr_example, x2)

position1, position2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

RESULT
(5, 2)
1
2

在我们的示例中：

1. 当我们在列表 ([1, 3, 4, 5, 7, 8, 9, 10, 12, 14, 15]) 中查找数字 8 时，我们找到它位于第 5 个位置（注意，这里的索引从 0 开始）。
2. 当我们在同一个列表中查找数字 4 时，我们找到它位于第 2 个位置。

这就是二分查找在 Python 中的实现。