轻松拿捏C语言——二分查找

用户11162265

发布于 2024-06-14 14:50:02

790

发布于 2024-06-14 14:50:02

文章被收录于专栏：C语言C语言

一、介绍

二分查找是一种在有序数组中查找某一特定元素的搜索算法。

举个生活中的例子，当我们要去图书馆借书时，知道了要找的图书编号，我们可以在一个大致范围的中间查找，然后在决定往前找还是往后找。这样就能比一本一本地找更加快速。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二、步骤

确定搜索范围，即数组的下标范围left和right。
计算中间元素的下标mid = (left + right) / 2(注意整数除法）。

但是像这样求平均值，如果数字太大了超过int类型能表示的最大范围，这种算法就会有问题，整数会溢出。所以我们可以换一个思路，把两数的差值的一半加到另一个数字中： mid = left + (right-left) /2

判断中间元素与目标值的大小关系。
- 如果相等，则返回中间元素的下标。
- 如果目标值小于中间元素，则在左半部分继续搜索（right = mid - 1）。
- 如果目标值大于中间元素，则在右半部分继续搜索（left = mid + 1）。
- 如果搜索范围left大于right，则表示数组中没有目标值，返回-1或其他表示未找到的值。

三、代码

法一：用递归实现

#include <stdio.h>  
  
int Sort(int arr[], int left, int right, int Key) {  
    if (left > right) 
        return -1; // 搜索范围无效  
    int mid = left + (right - left) / 2;  //这种写法可避免溢出
    if (arr[mid] == Key) 
    {  
        return mid; // 找到目标，返回下标  
    } 
    else if (arr[mid] > Key) 
    {  
        return Sort(arr, left, mid - 1, Key); // 在左半部分继续搜索  
    } 
    else 
    {  
        return Sort(arr, mid + 1, right, Key); // 在右半部分继续搜索  
    }  
}  
  
int main() {  
    int arr[] = {1, 3, 5, 7, 9};  
    int key = 5;  
    int n = sizeof(arr) / sizeof(arr[0]);  
    int ret = Sort(arr, 0, n - 1, key);  
    if (ret != -1) 
    {  
        printf("元素 %d 在数组中的下标为 %d\n", key, ret);  
    } 
    else 
    {  
        printf("元素 %d 不在数组中\n",key);  
    }  
    return 0;  
}

法二：用循环实现

#include <stdio.h>  
  
int Sort(int arr[], int N, int Key) 
{  
    int left = 0;
    int right = N - 1;  
    while (left <= right) 
    {  
        int mid = left + (right - left) / 2;  
        if (arr[mid] == Key) 
        {  
            return mid;  
        } 
        else if (arr[mid] > Key)
        {  
            right = mid - 1;  
        }
        else
        {  
            left = mid + 1;  
        }  
    }  
    return -1; // 未找到目标值  
}  
  
int main()
{  
    int arr[] = {1, 3, 5, 7, 9};  
    int key = 5;  
    int n = sizeof(arr) / sizeof(arr[0]);  
    int ret = Sort(arr, n, key);  
    if (ret != -1) 
    {  
        printf("元素 %d 在数组中的下标为 %d\n", key, ret);  
    } 
    else 
    {  
        printf("元素 %d 不在数组中\n",key);  
    }  
    return 0;   
}

使用循环的方式来实现二分查找，更直观且易于理解。

不过，递归的方式在某些情况下可能更简洁。

无论使用哪种方式，都需要确保数组是有序的，因为二分查找的前提是有序数组。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-14，如有侵权请联系 cloudcommunity@tencent.com 删除

算法