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

目录

（在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，这时候可能不太适合使用二分查找，因为我们的内存都是离散的，可能电脑没有这么多的内存。