【C语言】二分查找算法代码介绍

布满荆棘的人生 2024-03-23 17:47 116阅读 0赞

> 二分法查找是一种在有序数组中查找目标元素的高效算法。它的原理是通过将数组不断地分成两半，然后确定目标元素在哪一半中，从而缩小查找范围，直到找到目标元素或者确定目标元素不存在为止。  
> ![在这里插入图片描述][76ae35ee48404be79f9f49ff1393c747.png]

#### 文章目录 ####

*   *  1.实现细节
     *  2.代码示例
     *  3.代码解释

### 1.实现细节 ###

1.  首先，需要确定待查找的数组和目标元素。假设数组为arr，目标元素为target。
2.  确定数组的起始位置left和结束位置right。初始时，left为0，right为数组长度减一。
3.  进入循环，判断left是否小于等于right。如果是，则继续进行查找；否则，说明目标元素不存在，查找结束。
4.  在循环中，首先计算数组的中间位置mid，可以使用以下公式：mid = (left + right) / 2。
5.  然后，比较中间位置的元素arr\[mid\]与目标元素target的大小关系。
    
     *  如果arr\[mid\]等于target，说明找到了目标元素，返回mid即可。
     *  如果arr\[mid\]大于target，说明目标元素在数组的左半部分，将right更新为mid-1。
     *  如果arr\[mid\]小于target，说明目标元素在数组的右半部分，将left更新为mid+1。
6.  继续循环，直到找到目标元素或者确定目标元素不存在。

### 2.代码示例 ###

#include <stdio.h>
    
    int binarySearch(int arr[], int target, int left, int right) {
        
        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;
            }
        }
    
        return -1;  // 目标元素不存在
    }
    
    int main() {
        
        int arr[] = {
        1, 3, 5, 7, 9};
        int target = 5;
        int size = sizeof(arr) / sizeof(arr[0]);
        int result = binarySearch(arr, target, 0, size - 1);
    
        if (result == -1) {
        
            printf("目标元素不存在\n");
        } else {
        
            printf("目标元素在数组中的索引为：%d\n", result);
        }
    
        return 0;
    }

### 3.代码解释 ###

当我们使用二分法查找时，我们需要传入一个有序数组、目标元素以及数组的起始和结束索引作为参数。代码中的 `binarySearch` 函数就是用来实现二分法查找的。

首先，函数会判断起始索引是否大于结束索引，如果是，则说明目标元素不存在于数组中，返回 -1。这是递归终止条件。

接着，函数会计算数组的中间索引 `mid`，通过 `(start + end) / 2` 计算得到。然后，函数会比较中间索引对应的元素 `arr[mid]` 和目标元素 `target` 的大小关系。

*  如果 `arr[mid]` 等于 `target`，则说明目标元素已经找到，返回 `mid`。
 *  如果 `arr[mid]` 大于 `target`，则说明目标元素在数组的左半部分，我们需要在左半部分继续查找，调用递归函数 `binarySearch(arr, target, start, mid - 1)`。
 *  如果 `arr[mid]` 小于 `target`，则说明目标元素在数组的右半部分，我们需要在右半部分继续查找，调用递归函数 `binarySearch(arr, target, mid + 1, end)`。

通过不断缩小查找范围，函数会在有序数组中找到目标元素的索引，或者确定目标元素不存在于数组中。

在 `main` 函数中，我们定义了一个有序数组 `arr` 和目标元素 `target`。然后，我们调用 `binarySearch` 函数进行二分法查找，并将返回的结果保存在变量 `result` 中。

最后，我们根据 `result` 的值进行判断，如果为 -1，则说明目标元素不存在于数组中，否则输出目标元素在数组中的索引。

二分法查找的时间复杂度为O(logN)，其中N为数组的长度。相比于线性查找的时间复杂度O(N)，二分法查找的效率更高。因此，在大规模数据的查找中，二分法查找是一种非常有效的算法。

[76ae35ee48404be79f9f49ff1393c747.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/71dd9a08699f4c68b304a05fbbfdfc6a.png