【数据结构与算法】【查找】折半查找（二分查找）的代码实现

柔光的暖阳◎ 2022-08-13 15:46 204阅读 0赞

**折半查找**（Binary Search）：也称为 **二分查找**。它的前提是：1、线性表中的记录必须是关键字有序（通常是从小到大有序）；2、线性表必须采用顺序存储。

**折半查找的基本思想**是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定 值大于中间记录的关键字，则在中间记录的右半区继续查找。不断反复，直到查找成功；或者直到最后都没有找到，查找失败。

**mid计算公式**：mid = (low + high) / 2 = low + (high - low) / 2;

折半查找的有序表，对应折半查找判定二叉树的中序遍历。

代码实现：

// Filename: binary_search.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "public.h"
    
    // 折半查找（二分查找）
    // a[n]为待查找数组，a[0]不使用，n为数组长度（不包含a[0]）
    // 查找成功，则返回key所在的地址；查找失败，则返回0
    int BinarySearch(int a[], int n, int key)
    {
        int low = 1, high = n, mid;
    
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (key < a[mid])
            {
                high = mid - 1;
            }
            else if (key > a[mid])
            {
                low = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return 0;
    }
    
    // 折半查找（二分查找）主函数
    int BinarySearchMain()
    {
        int value;
        int retval;
        int arr[12] = {0xFF, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1};
    
        printf("折半查找（二分查找）演示(a[0]未使用，不参与排序): \n");
    
        printf("静态查找表数据：\n");
        PrintArray(arr, sizeof(arr) / sizeof(int));
        printf("\n");
    
        while (1)
        {
            // 查找元素
            printf("请输入要查找的数据: \n");
            scanf("%d", &value);
            // 退出查找
            if (0xFF == value) break;
    
            retval = BinarySearch(arr, 3, value);
    
            if (0 == retval)
            {
                printf("查找失败!\n");
            }
            else
            {
                printf("查找成功，元素所在位置: %d.", retval);
            }
        }
    
        return 0;
    }