使用c语言编写一个程序,实现二分查找算法

2023-12-29 13:21:43

目录

(在c语言代码中)二分查找算法需要注意的六点

关于乱序数组时二分查找的使用方法

(适用于正序数组)的代码:

(适用于有规律乱序数组)的代码:

关于二分查找的算法设计思想


(在c语言代码中)二分查找算法需要注意的六点

在使用二分查找算法的C语言代码中,有几个需要注意的地方:

  1. 数组必须是有序的:二分查找算法要求在每一次比较中,能够确定目标元素位于左半部分还是右半部分因此,在使用二分查找之前,必须确保数组是按照升序或降序排列的。

  2. 确定查找范围:二分查找算法使用两个指针(left和right)来确定查找范围。初始时,left指向数组的第一个元素right指向数组的最后一个元素。在每一次迭代中,根据中间元素的值与目标元素的关系,更新left和right的值,缩小查找范围

  3. 防止整数溢出:在计算mid值时,使用 mid = left + (right - left) / 2 的方式可以避免整数溢出。这样做可以确保即使left和right非常大,它们的和也不会超过整型变量的上限。

  4. 循环条件和退出条件:循环条件通常是 left <= right,当left和right相等时,还需要进行一次比较来确定是否找到了目标元素。如果找到了目标元素,则返回其索引;如果没有找到目标元素,则返回-1表示未找到。

  5. 处理找不到目标元素的情况:如果二分查找算法无法找到目标元素,需要在最后返回一个特定的值(例如-1)来表示未找到。这样的处理方式可以让调用者知道目标元素不存在于数组中。

  6. 注意边界条件:在编写代码时,要特别注意处理边界条件,例如空数组、只有一个元素的数组等特殊情况

以上是使用二分查找算法时需要注意的几个地方。通过遵循这些注意事项,可以确保二分查找算法的正确性和可靠性

关于乱序数组时二分查找的使用方法

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 我相信很多人都想问那如果不是有序的该怎么办呢?

  • 如果数组是有规律的但无序可以考虑使用一些变种的二分查找算法来实现目标元素的查找,

数组中存在部分有序的子数组(下面有详细代码说明):如果数组中存在部分有序的子数组,可以使用类似于旋转数组的处理方法,即先确定哪一部分是有序的,然后根据目标元素和有序部分的边界值的关系,来决定向左或向右缩小查找范围,从而实现在无序数组中进行二分查找。

  • 如果数组是完全乱序的(没有任何的规律)不能直接使用标准的二分查找算法。在这种情况下,可以考虑使用其他搜索算法,比如线性搜索或者哈希表等。
  1. 线性搜索:对于完全乱序的数组,最简单的方法是使用线性搜索,即逐个遍历数组中的元素,逐个进行比较,直到找到目标元素或者搜索完整个数组。虽然线性搜索的时间复杂度较高,但对于小型数据集或者不需要频繁搜索的情况下,是一种可行的选择。

  2. 哈希表:如果需要频繁地进行目标元素的查找操作,可以考虑使用哈希表来存储数组中的元素。将数组中的元素映射到哈希表中,并建立起元素与索引之间的映射关系。这样,在需要查找目标元素时,可以通过哈希表来快速找到目标元素的索引。

  3. 其他搜索算法:除了线性搜索和哈希表,还有一些其他适用于乱序数组的搜索算法,比如顺序统计量算法、随机化算法等。根据具体的需求和数据特点,可以选择适合的搜索算法来处理完全乱序的数组。

总之,对于完全乱序的数组,需要根据具体情况选择合适的搜索算法来实现目标元素的查找

(适用于正序数组)的代码:

#include <stdio.h>

int binarySearch(int arr[], int n, int target) 
{
    int left = 0;
    int right = n - 1;

    while (left <= right) 
    {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) 
        {
            return mid;  // 找到目标元素,返回索引
        }
        else if (arr[mid] < target) 
        {
            left = mid + 1;  // 目标元素在[mid+1, right]区间内
        }
        else 
        {
            right = mid - 1;  // 目标元素在[left, mid-1]区间内
        }
    }

    return -1;  // 目标元素不存在,返回-1
}

int main() 
{
    int arr[] = { 2, 3, 5, 7, 9, 11, 13, 17, 19, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int target;

    printf("请输入要查找的数字:");
    scanf("%d", &target);

    int result = binarySearch(arr, n, target);

    if (result != -1) 
    {
        printf("%d 在数组中的位置为:%d\n", target, result);
    }
    else 
    {
        printf("%d 不在数组中。\n", target);
    }

    return 0;
}

运行程序后,它会提示您输入要查找的数字。然后,程序将调用binarySearch()函数,在数组中使用二分查找算法查找目标数字,并输出结果。

binarySearch()函数中,我们使用了循环来不断缩小查找范围,直到找到目标元素或确定其不存在为止。

(适用于有规律乱序数组)的代码:

#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;  // 找到目标元素,返回索引
        }

        // 如果左半部分有序
        if (arr[left] <= arr[mid]) 
        {
            // 判断目标元素是否在左半部分
            if (arr[left] <= target && target < arr[mid]) 
            {
                right = mid - 1;  // 目标元素在[left, mid-1]区间内
            }
            else 
            {
                left = mid + 1;  // 目标元素在[mid+1, right]区间内
            }
        }
        // 如果右半部分有序
        else 
        {
            // 判断目标元素是否在右半部分
            if (arr[mid] < target && target <= arr[right])
            {
                left = mid + 1;  // 目标元素在[mid+1, right]区间内
            }
            else 
            {
                right = mid - 1;  // 目标元素在[left, mid-1]区间内
            }
        }
    }

    return -1;  // 目标元素不存在,返回-1
}

int main() 
{
    int arr[] = { 13, 19, 23, 2, 3, 5, 7, 9, 11, 17 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int target;

    printf("请输入要查找的数字:");
    scanf("%d", &target);

    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()函数中,我们首先判断左半部分是否有序如果是有序的,我们判断目标元素是否在左半部分,如果是,则将查找范围缩小至左半部分;如果不是,则将查找范围缩小至右半部分

如果左半部分不是有序的,那么右半部分必然是有序的。我们判断目标元素是否在右半部分,如果是,则将查找范围缩小至右半部分;如果不是,则将查找范围缩小至左半部分。

关于二分查找的算法设计思想

  • 二分查找的基本思想是将n个元素分成大致相等的两部分,取a [n/2]与x(要找的数字)做比较,

如果x=a [n/2],则找到x,算法中止;

如果x<a [n/2],则只要在数组a的左半部分继续搜索x,

如果x>a [n/2],则只要在数组a的右半部搜索x.

  • 二分查找的优点

二分查找比线性搜索更快,特别是对于大型数组。

比具有类似时间复杂度的其他搜索算法(例如插值搜索或指数搜索)更有效

二分查找非常适合搜索存储在外部存储器中的大型数据集,例如硬盘驱动器或云中。

  • 数据量太小不适合二分查找

如果要处理的数据量很小,完全没有必要用二分查找,顺序遍历就足够了。比如我们在一个大小为 10 的数组中查找一个元素,不管用二分查找还是顺序遍历,查找速度都差不多,只有数据量比较大的时候,二分查找的优势才会比较明显。

  • 数据量太大不适合二分查找

二分查找底层依赖的是数组,数组需要的是一段连续的存储空间,所以我们的数据比较大时,比如1GB,这时候可能不太适合使用二分查找,因为我们的内存都是离散的,可能电脑没有这么多的内存。

文章来源:https://blog.csdn.net/2301_79783133/article/details/135260879
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。