查找是在一组元素中找到一个元素出现的过程。有许多用于查找的技术，二分查找就是其中之一。在查找中，算法测试列表中是否有匹配项，并返回找到匹配项的索引，否则会给出列表中未找到该元素的消息。
二分查找算法也称为“半区间算法”或“对数算法”。它适用于排序数组，如果给定数组未排序，则需要先对元素进行排序，然后在其上实现查找。该算法采用分治法。它首先将列表分为两部分，通过取列表的中间元素并检查查找元素是否与中间元素匹配。如果两者相等，则返回索引，否则，算法选择其中一个子列表，其中查找元素出现的可能性更大。这种子列表的划分和查找将一直持续到子列表的大小减小到零。
它在大型列表上的工作速度比小型列表快。二分查找树和B树数据结构基于二分查找。数组重复对半划分将二分查找的时间复杂度降低到 O(logn)。
函数来实现 Python 中的二分查找。数组和搜索项可以作为输入变量传递给函数。while 循环首先计算中间元素，然后检查返回中间索引函数中将 -1 作为最后一条语句返回函数，并根据函数的返回值打印结果现在，让我们看看二分查找算法的工作原理。取一个数组 [ 12, 23, 26, 34, 38, 41 ] 并搜索元素 34。我们有 12 在开始，41 在最后，26 在中间。检查中间的 26<34。这是真的，所以要搜索的列表变为 [34, 38, 41 ]，即右子数组。检查 38<34，不，然后检查 38>34，是真的，所以现在列表变为 [34] 并找到匹配项，因此我们的搜索成功了。
步骤 1: 编写一个函数 binarySearch，带变量数组 arr 和搜索值 item。
步骤 2: 初始化变量 low 为 0 和 high 为最后一个索引
步骤 3: 启动一个while 循环，重复直到条件 low<=high，
步骤 4: 找到数组 arr 的中间索引 mid 并检查中间元素 < item，如果匹配则重置 low=mid+1（右子数组）
步骤 5: 否则检查中间元素 > item，如果匹配则重置 high=mid-1（左子数组）
步骤 6: 否则返回 mid 表示找到匹配项
步骤 6: 现在通过返回 -1 结束函数，表示未找到匹配项
步骤 7: 初始化一个带值的数组 arr 和要搜索的 item
步骤 8: 调用 binarySearch()，带值 arr，item 并检查返回值并打印合适的结果
def binary_search(arr, item):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# If item is greater, ignore left half
if arr[mid] < item:
low = mid + 1
# If item is smaller, ignore right half
elif arr[mid] > item:
high = mid - 1
# means item is present at mid
else:
return mid
# If we reach here, then the element was not present
return -1
# Test array
arr = [ 12, 23, 26, 34, 38, 41 ]
item = 34
# Function call
result = binary_search(arr, item)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")
Element is present at index 3
