数据结构与算法之二分搜索算法

二分搜索算法是一种常用的搜索算法，它可以在有序序列中查找指定元素，时间复杂度为 O(log n)。

二分搜索算法的原理是： 在有序序列中查找指定元素时，先取序列的中间位置元素，将其与指定元素进行比较，如果相等，则查找成功；如果中间位置元素大于指定元素，则在序列左半部分继续查找；否则，在右半部分继续查找。如此重复进行，直到找到指定元素或者查找完整个序列为止。

具体实现过程如下：

1. 确定序列的起始和结束位置；
2. 计算序列的中间位置；
3. 比较中间位置元素和指定元素的大小关系；
4. 如果相等，则查找成功，返回元素下标；
5. 如果中间位置元素大于指定元素，则在左半部分继续查找，更新结束位置为中间位置；
6. 如果中间位置元素小于指定元素，则在右半部分继续查找，更新起始位置为中间位置；
7. 如此重复进行，直到找到指定元素或者查找完整个序列为止。

二分搜索算法适用于有序数组或者有序链表，对于无序序列则不适用。在实际应用中，二分搜索算法常用于快速查找有序序列中的元素，比如二分查找算法常用于搜索引擎中的关键词查找。

一、C 实现二分搜索算法及代码详解

二分搜索算法（也称为二分查找算法）是一种在有序数组中查找特定元素的搜索算法。该算法将数组中间的元素与目标元素进行比较，如果相等则返回该元素的索引，如果小于目标元素，则在数组的右半部分继续搜索；如果大于目标元素，则在数组的左半部分继续搜索。重复执行此过程直到找到目标元素或者确定目标元素不存在。

C 代码实现：

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int x) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果目标元素在数组中间，则返回其索引
        if (arr[mid] == x)
            return mid;

        // 如果目标元素小于数组中间元素，则在左半部分继续查找
        if (arr[mid] > x)
            right = mid - 1;

        // 如果目标元素大于数组中间元素，则在右半部分继续查找
        else
            left = mid + 1;
    }

    // 如果目标元素不存在于数组中，则返回 -1
    return -1;
}

int main() {
    int arr[] = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 23;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        printf("Element is not present in array\n");
    else
        printf("Element is present at index %d\n", result);

    return 0;
}

在上面的代码中，我们使用了 while 循环来实现二分搜索算法。其中，left 和 right 表示当前搜索区间的左右端点，x 表示要查找的目标元素。在循环中，我们首先计算中间位置 mid，然后将目标元素与该位置的元素进行比较。如果相等，则直接返回 mid；如果目标元素小于中间元素，则继续在左半部分搜索；如果目标元素大于中间元素，则继续在右半部分搜索。重复执行此过程直到找到目标元素或者确定目标元素不存在。

如果目标元素不存在于数组中，则返回 -1。否则，返回该元素在数组中的索引。

例如，上面的代码中，我们要查找数组 {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} 中是否存在元素 23。程序输出：

Element is present at index 5

这表示元素 23 在数组中的索引为 5。

二、C++ 实现二分搜索算法及代码详解

二分搜索（Binary Search）算法是一种高效的查找算法，适用于有序数组中查找某个元素的位置。其基本思路是，将有序数组不断地二分，直到找到目标元素或确定目标元素不存在。

以下是 C++ 实现二分搜索的代码及详解：

int binarySearch(int arr[], int target, int left, int right) {
    // 首先判断搜索范围是否有效
    if (left > right) {
        return -1;
    }
    
    // 计算中间位置
    int middle = left + (right - left) / 2;
    
    // 比较中间位置的值与目标值的关系
    if (arr[middle] == target) {
        // 如果中间位置的值等于目标值，则返回中间位置
        return middle;
    } else if (arr[middle] > target) {
        // 如果中间位置的值大于目标值，则在左侧继续搜索
        return binarySearch(arr, target, left, middle - 1);
    } else {
        // 如果中间位置的值小于目标值，则在右侧继续搜索
        return binarySearch(arr, target, middle + 1, right);
    }
}

该函数接受四个参数：数组 arr、目标值 target、搜索区间左端点 left 和搜索区间右端点 right。

首先判断搜索区间是否有效，如果左端点大于右端点，则搜索区间无效，返回 -1。

然后计算中间位置 middle，使用数组下标访问该位置，与目标值比较。如果相等，说明已经找到目标值，直接返回中间位置；如果中间位置的值大于目标值，说明目标值在数组的左侧，递归搜索左侧区间；如果中间位置的值小于目标值，说明目标值在数组的右侧，递归搜索右侧区间。在递归搜索时，更新搜索区间的左右端点即可。

使用示例：

int arr[] = { 1, 3, 5, 7, 9 };
int n = sizeof(arr) / sizeof(int);
int target = 5;
int result = binarySearch(arr, target, 0, n - 1);

其中，数组 arr 是有序的，在该数组中查找目标值 5，搜索区间从下标 0 开始到下标 n - 1，即整个数组。

运行结果为 2，表示目标值在数组的下标为 2 的位置。

三、Java 实现二分搜索算法及代码详解

二分搜索算法（也称为二分查找）是一种查找算法，用于在已排序的数组中找到特定元素的位置。该算法将目标元素与数组中间位置的元素进行比较，如果相等，则返回该位置；如果目标元素小于中间元素，则继续在左半部分进行搜索；如果目标元素大于中间元素，则继续在右半部分进行搜索。这个过程不断重复，直到找到目标元素或确定没有目标元素。

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

public class BinarySearch {
    public static int search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // 如果没有找到则返回 -1
        return -1;
    }
}

这个方法接受一个已排序的整数数组和一个目标整数作为参数，并返回目标整数在数组中的位置。如果目标整数不在数组中，则返回 -1。

在主方法中，可以创建一个测试数组并调用 search 方法：

public static void main(String[] args) {
    int[] arr = {1, 3, 5, 7, 9};
    int target = 5;
    int result = BinarySearch.search(arr, target);
    System.out.println(result);  // 输出 2
}

在该示例中，将搜索目标整数 5 的位置，返回结果为 2，表示目标整数位于数组中的第三个位置。