二分搜索算法实现python

二分搜索算法是一种在有序数组中查找特定元素的搜索算法。它的实现可以使用递归或迭代的方式。

下面是一个使用递归实现的二分搜索算法的Python代码：

class BinarySearch(object):
    def binary_search(self, array, data):
        """二分查找法递归实现"""
        if len(array) == 0:
            return False
        array.sort()
        mid_index = len(array) // 2
        if array[mid_index] == data:
            return True
        return self.binary_search(array[mid_index+1:], data) if data > array[mid_index] else \
            self.binary_search(array[:mid_index], data)

这段代码中，我们首先对数组进行排序，然后计算出中间元素的索引。如果中间元素与目标值相等，就返回True。否则，根据目标值与中间元素的大小关系，将搜索范围缩小为左半部分或右半部分，并递归调用二分搜索函数。

相关问题

python实现二分搜索算法

二分搜索算法，也称折半搜索，是一种在有序数组中查找某一特定元素的搜索算法。它的基本思想是，将数组中间位置的元素与目标值进行比较，如果相等，则返回索引；如果目标值小于中间元素，则在数组左半部分继续查找；如果目标值大于中间元素，则在数组右半部分继续查找。重复以上过程，直到找到目标值或者数组被遍历完。

以下是 Python 实现二分搜索算法的代码：

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

其中，arr 是有序数组，target 是要查找的目标值。该函数返回目标值在数组中的索引，如果目标值不存在，则返回 -1。

实现过程中，首先定义左右两个指针，分别指向数组的起始位置和结束位置。然后在循环中计算中间位置 mid，并将其与目标值进行比较。如果相等，则返回 mid；如果目标值小于中间元素，则将右指针移动到 mid - 1 的位置，继续在左半部分查找；如果目标值大于中间元素，则将左指针移动到 mid + 1 的位置，继续在右半部分查找。重复以上步骤，直到找到目标值或者数组被遍历完。如果目标值不存在，则返回 -1。

二分搜索算法python

下面是一个使用二分搜索算法在Python中查找有序列表中特定元素的示例代码：

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
        mid = (high + low) // 2
 
        if arr[mid] < x:
            low = mid + 1
 
        elif arr[mid] > x:
            high = mid - 1
 
        else:
            return mid
 
    return -1
 
 
arr = [2, 3, 4, 10, 40]
x = 10
 
result = binary_search(arr, x)
 
if result != -1:
    print("元素在索引 %d" % result)
else:
    print("元素不在数组中")

在上面的示例中，我们定义了一个名为 `binary_search` 的函数，它接受两个参数：一个有序数字列表和要搜索的元素 `x`。

在函数中，我们初始化 `low` 和 `high` 变量来表示要搜索的数字列表的范围。我们还创建一个 `mid` 变量来表示中间元素的索引。

在 while 循环中，我们首先计算中间元素的索引。如果这个中间元素小于我们要查找的元素 `x`，那么我们将 `low` 变量设置为 `mid + 1`，这样我们就可以继续在右边的子数组中查找。如果这个中间元素大于我们要查找的元素 `x`，那么我们将 `high` 变量设置为 `mid - 1`，这样我们就可以继续在左边的子数组中查找。如果这个中间元素正好是我们要查找的元素 `x`，我们就返回它的索引。

如果我们在 while 循环中没有找到要查找的元素，则返回 -1，表示该元素不在数字列表中。

在我们的示例中，我们创建了一个有序数字列表 `[2, 3, 4, 10, 40]`，并试图查找数字 `10` 的索引。由于数字 `10` 存在于该列表中，我们最终会打印出 `元素在索引 3`。如果我们尝试查找数字 `5` 的索引，我们会得到 `元素不在数组中` 的输出。