二分查找的递归和非递归算法（C语言实现）

蔚落 2022-06-02 06:40 248阅读 0赞

# 二分查找的用途 #

二分查找又称折半查找，它用来解决“在一堆数中找出指定的数（也可能找了，发现没有）”这类问题。

# 二分查找的应用条件 #

要应用二分查找，这“一堆数”必须有以下特征：

1.  存储在数组中
2.  有序排列

所以，如果数是用链表存储的，那就无法在其上应用二分查找。  
至于是升序排列还是降序排列、数组中是否存在相同的元素都不要紧。在本文的实验中，我们使数组递增排列，且数组中的元素互不相同。

# 二分查找的算法描述 #

在算法思想上，二分查找属于减治法。  
假设含有`n`个元素的数组（下标从`[0]`至`[n-1`\]）中的元素已经按照升序排列。首先比较查找键值`K`和数组中间位置元素`a[mid]`，如果它们相等，算法结束。否则，如果`K`<`a[mid]`，则对数组前半部分（`a[0]`~`a[mid-1]`）执行该操作；如果`K`>`a[mid]`，则对数组的后半部分（`a[mid+1]`~`a[n-1]`）执行该操作。

# C语言实现 #

先贴出核心代码，在本文的最后会贴出包含注释的完整代码。

## 非递归解法 ##

int binary_search(const int b[], int search_key, int low, int high)
    {
    
       while (low <= high) {    
          int mid = (low + high) / 2;
    
          if (search_key == b[mid]) {                       
             return mid; //找到后返回下标 
          }  
          else if (search_key < b[mid]) {                    
             high = mid - 1;   
          }                                        
          else {                                                     
             low = mid + 1;       
          }                                            
       } 
    
       return -1; //没有找到
    }

要点分析：

*  `while (low <= high)`表示不断循环，直到`low`比`high`大。当`low`>`high`时表示查找区间为空，此时返回`-1`，表示没有找到。
 *  `int mid = (low + high) / 2;`这句话可能会导致整数溢出，更好的写法是`int mid = low + (high - low) / 2;`

## 递归解法 ##

int binary_search_recursive(const int b[], int search_key, int low, int high)  
    {  
        if (low > high)  
            return -1;  
    
        int mid = low + (high - low) / 2;  //防止溢出
    
        if (search_key == b[mid])  
            return mid;     
        else if (search_key < b[mid])  
            return binary_search_recursive(b, search_key, low, mid - 1);    
        else  
            return binary_search_recursive(b, search_key, mid + 1, high);  
    }

## 完整代码及测试结果 ##

【操作系统】： Ubuntu 14.04.3  
【编译器】：gcc 4.8.4

#include <stdio.h>
    #define SIZE 15
    
    // function prototypes
    void print_header(void);
    void print_row(const int b[], int low, int mid, int high);
    int binary_search(const int b[], int search_key, int low, int high);
    int binary_search_recursive(const int b[], int search_key, int low, int high);  
    
    
    int main(void)
    {
        int a[SIZE]; // create array a
    
       // create data
        for (int i = 0; i < SIZE; ++i) {
            a[i] = 2 * i;
        }    
    
        printf("%s %d: ", "Enter a number between 0 and",a[SIZE-1]);
        int key; // value to locate in array a
        scanf("%d", &key);
    
        puts("\nNon-recursive solution");
    #ifdef SHOW_PROCEDURE
        print_header(); //打印出查找的过程
    #endif
        // Non-recursive solution
    
        int result = binary_search(a, key, 0, SIZE - 1);
    
        // display results
        (result == -1) ? printf("\n%d not found\n", key) : \
        printf("\n%d found at index %d\n", key, result);
    
        puts("\nRecursive solution");
    #ifdef SHOW_PROCEDURE
        print_header();
    #endif
        // Recursive solution
        result = binary_search_recursive(a, key, 0, SIZE - 1);
    
        // display results
        (result == -1) ? printf("\n%d not found\n", key) : \
        printf("\n%d found at index %d\n", key, result);
    
    }
    
    // function to perform binary search of an array
    int binary_search(const int b[], int search_key, int low, int high)
    {
       // loop until low index is greater than high index
        while (low <= high) {
    
            // determine mid element of subarray being searched
            int mid = (low + high) / 2;
    #ifdef SHOW_PROCEDURE
            // display subarray used in this loop iteration
            print_row(b, low, mid, high);
    #endif
            // if search_key matched mid element, return mid
            if (search_key == b[mid]) {                       
                return mid;                                       
            }                                           
    
            // if search_key is less than mid element, set new high
            else if (search_key < b[mid]) {                    
                high = mid - 1; // search low end of array 
            }                                     
    
            // if search_key is greater than mid element, set new low
            else {                                                     
                low = mid + 1; // search high end of array 
            }                                            
        } // end while
    
        return -1; // search_key not found
    } 
    
    
    int binary_search_recursive(const int b[], int search_key, int low, int high)  
    {  
        if (low > high)  
            return -1;  
    
        int mid = low + (high - low) / 2;  //防止溢出
    
    #ifdef SHOW_PROCEDURE
          // display subarray used in this loop iteration
          print_row(b, low, mid, high);
    #endif
    
        if (search_key == b[mid])  
            return mid;  
    
        else if (search_key < b[mid])  
            return binary_search_recursive(b, search_key, low, mid - 1);  
    
        else  
            return binary_search_recursive(b, search_key, mid + 1, high);  
    
    }  
    
    
    // Print a header for the output
    void print_header(void)
    {
        puts("index:");
    
        // output column head
        for (int i = 0; i < SIZE; ++i) {
            printf("%3d ", i);
        } 
    
        puts(""); // start new line of output
    
        // output line of - characters , 1个索引占4个“-”
        for (int i = 1; i <= 4 * SIZE; ++i) {
            printf("%s", "-");
        } 
    
        puts(""); // start new line of output
    } 
    
    // Print one row of output showing the current
    // part of the array being processed.
    void print_row(const int b[], int low, int mid, int high)
    {
       // loop through entire array
        for (int i = 0; i < SIZE; ++i) {
    
            // display spaces if outside current subarray range
            if (i < low || i > high) {
                printf("%s", " "); //4个空格
            }  
            else if (i == mid) { // display mid element
                printf("%3d*", b[i]); // mark mid value
            } 
            else { // display other elements in subarray
                printf("%3d ", b[i]);
            } 
        } 
    
        puts(""); // start new line of output
    }

编译上面的文件（假设文件名是`binary_search.c`）

gcc binary_search.c -std=gnu99 -DSHOW_PROCEDURE

`-DSHOW_PROCEDURE`表示定义宏`SHOW_PROCEDURE`，相当于在源文件里面写`#define SHOW_PROCEDURE`.

`main`函数中生成数组的代码是：

#define SIZE 15
    
        int a[SIZE]; 
        for (int i = 0; i < SIZE; ++i) {
            a[i] = 2 * i;
        }

由此可见，生成了一个以升序排列的数组——`{0,2,4,6,8,...,26,28}`，共15个元素。

运行程序后，会让用户输入键值。`*`表示处于中间位置的元素`a[mid]`。

![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

![这里写图片描述][SouthEast 2]

【参考资料】  
《C How to Program （8th Edition）》

[SouthEast]: /images/20220602/3e0f6551d1074df39120e8f82040b58c.png
[SouthEast 1]: /images/20220602/72b75a4515e4458488a93cd9ed0228ee.png
[SouthEast 2]: /images/20220602/0816aa33888e4827b28522639d6a90cb.png