二分查找的简单例题及解析

二分查找是一种常见且高效的查找算法，尤其在有序列表中使用广泛。本文将通过一个具体的例子来介绍二分查找的操作步骤及其时间复杂度，并对其应用进行简单分析。

假设有一个有序列表[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]，现在我们需要使用二分查找算法来查找其中的一个元素，比如15。

第一步，我们需要确定要查找的元素在有序列表中的范围，即确定起始和结束位置。我们可以设一个变量low表示列表的第一个位置，一个变量high表示列表的最后一个位置，而mid则表示中间位置，即mid = (low+high)//2。

第二步，比较中间位置的元素与要查找的元素的大小，如果两者相等，说明找到了目标元素，返回该元素的位置。

如果中间位置的元素大于要查找的元素，说明目标元素在列表的前半部分（low~mid-1）中，此时更新high = mid-1，继续进行下一轮查找。

如果中间位置的元素小于要查找的元素，说明目标元素在列表的后半部分（mid+1~high）中，此时更新low = mid+1，继续进行下一轮查找。

第三步，如果low > high，则说明查找失败，返回-1。

下面是使用Python语言实现二分查找的代码：

```

def binary_search(arr, target):

low, high = 0, len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == target:

return mid

elif arr[mid] > target:

high = mid - 1

else:

low = mid + 1

return -1

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]

target = 15

print(binary_search(arr, target)) # 输出7，即15在列表的第8个位置

```

在以上例子中，我们可以发现二分查找算法的时间复杂度为O(logn)，其中n为列表的长度。这是因为每一轮查找都能将待查找的元素范围缩小一半，所以最多需要logn轮查找。与顺序查找的时间复杂度O(n)相比，二分查找算法的效率要高得多。

当然，二分查找算法并不是万能的。它最适用于静态查找，即列表的元素不发生新增或删除，且查找次数较多的情况下。如果列表元素经常变动，就需要使用其他更适合的算法，如散列表等。

总之，二分查找是一种高效且实用的算法，在实际应用中具有很大的价值和意义。