二分查找算法（数据结构）

二分查找算法，也称折半查找算法，是一种在有序数组中查找某一特定元素的搜索算法。该算法的时间复杂度为O(log n)。

以下是二分查找算法的实现步骤：
1. 确定数组的左右边界，即最小下标和最大下标。
2. 计算数组的中间位置，即中间下标。
3. 比较中间位置的值与目标值的大小关系，如果相等则返回中间位置，如果中间位置的值大于目标值，则在左半部分继续查找，否则在右半部分继续查找。
4. 重复步骤2和步骤3，直到找到目标值或者左边界大于右边界。

以下是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:
            right = mid - 1
        else:
            left = mid + 1
    return -1

相关问题

数据结构二分查找算法

二分查找是一种常见的搜索算法，用于在有序数组或有序列表中快速定位特定值的位置。这种算法的基本思想是将目标值与数组中间元素进行比较，根据比较结果将搜索范围缩小一半，直到找到目标值或确定目标值不存在为止。

以下是二分查找算法的基本步骤：
1. 初始化左边界 left 和右边界 right，分别指向数组的第一个元素和最后一个元素。
2. 计算中间位置 mid，可以使用公式 mid = (left + right) / 2。
3. 比较中间位置的值与目标值 target：
- 如果中间位置的值等于目标值，则找到目标值，返回索引。
- 如果中间位置的值大于目标值，则目标值可能在左半部分，更新右边界为 mid - 1。
- 如果中间位置的值小于目标值，则目标值可能在右半部分，更新左边界为 mid + 1。
4. 重复步骤 2 和步骤 3，直到找到目标值或搜索范围为空（即 left > right）。

以下是一个使用二分查找算法在有序数组中查找目标值的示例代码（使用递归实现）：

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

你可以将目标值、数组以及左右边界作为参数传递给该函数来执行二分查找。如果目标值存在于数组中，该函数将返回目标值的索引；否则，返回 -1 表示未找到。

希望这能回答你的问题！如有其他疑问，请随时提问。

数据结构二分查找算法C语言

二分查找算法是一种在有序数组中快速定位目标值的有效算法。以下是一个使用C语言实现的二分查找算法示例：

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    
    return -1; // 当目标值不存在于数组中时，返回-1
}

int main() {
    int arr[] = {2, 4, 7, 10, 14, 18, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    
    int result = binarySearch(arr, 0, n - 1, target);
    
    if (result != -1) {
        printf("目标值 %d 在数组中的索引位置为 %d\n", target, result);
    }
    else {
        printf("目标值 %d 不存在于数组中\n", target);
    }
    
    return 0;
}

在这个示例中，我们定义了一个 `binarySearch` 函数来执行二分查找算法。函数接受一个有序数组 `arr`，查找范围的左边界 `left`，查找范围的右边界 `right`，以及目标值 `target`。算法通过不断调整查找范围的左右边界，将目标值与中间元素进行比较，缩小查找范围，最终找到目标值或确定其不存在。

在 `main` 函数中，我们定义了一个有序数组 `arr`，计算数组的长度并设置目标值为10。然后调用 `binarySearch` 函数进行查找，并根据返回结果输出相应的信息。

以上是一个简单的二分查找算法的C语言实现示例。希望能够帮助你理解二分查找算法的基本思想和实现方式。