【算法四】——线性查找和折半查找

约定不等于承诺〃 2022-05-30 08:38 217阅读 0赞

### 线性查找 ###

有些查找问题要用时间复杂度为O(n)的算法来解决。例如写一个indexof函数，从任意输入字符串中找出某个字母的位置并返回这个位置，如果找不到就返回-1：

例： 线性查找

#include <stdio.h>
    
    char a[]="hello world";
    
    int indexof(char letter)
    {
    	int i = 0;
    	while (a[i] != '\0')
    	{
    		if(a[i] == letter)
    			return i;
    		i++;
    	}
    	return -1;
    }
    
    int main(void)
    {
    	printf("%d %d\n", indexof('o'), indexof('z'));
    	return 0;
    }

这个实现是最直观和最容易想到的，但它是不是最快的算法呢？我们知道插入排序也比归并排序更容易想到，但通常不如归并排序快。那么现在这个问题－－给定一个随机排列的序列，找出其中某个元素的位置－－有没有比O(n)更快的算法？比如O(lgn)？

### 折半查找 ###

如果不是从一组随机的序列里查找，而是从一组排好序的序列里找出某个元素的位置，则可以有更快的算法：

例：折半查找

#include <stdio.h>
    
    #define LEN 8
    int a[LEN] = {1, 2, 2, 2, 5, 6, 8, 9};
    
    int binarysearch(int number)
    {
    	int mid, start = 0, end = LEN -1;
    	
    	while (start <= end)
    	{
    		mid = (start + end)/2;
    		if(a[mid] < number)
    			start = mid + 1;
    		else if (a[mid] > number)
    			end = mid -1;
    		else
    			return mid;
    	}
    	return -1;
    }
    
    int main(void)
    {
    	printf("%d\n", binarysearch(5));
    	return 0;
    }

由于这个序列已经从小到大排好序了，每次取中间的元素和待查找的元素比较，如果中间的元素比待查找的元素小，就说明“如果待查找的元素存在，一定位于序列的后半部分”，这样可以把搜索范围缩小到后半部分，然后再次使用这种算法迭代。这种“每次将搜索范围缩小一半”的思想称为折半查找（Binary Search）。思考一下，这个算法的时间复杂度是多少？

我们讲过借助Loop Invariant证明循环的正确性，binarysearch这个函数的主体也是一个循环，它的Loop Invariant可以这样描述：待查找的元素number如果存在于数组a之中，那么一定存在于a\[start..end\]这个范围之间，换句话说，在这个范围之外的数组a的元素中一定不存在number这个元素。以下为了书写方便，我们把这句话表示成mustbe(start, end, number)。可以一边看算法一边做推理：

int binarysearch(int number)
    {
            int mid, start = 0, end = LEN -1;
    
            /* 假定a是排好序的 */
            /* mustbe(start, end, number),因为a[start...end]就是整个数组a[0...LEN-1] */
            while (start <= end)
            {
            /*mustbe(start, end, number), 因为一开始进入循环时是正确的，每次循环也都维护了这个条件  */
                    mid = (start + end)/2;
                    if(a[mid] < number)
            /*既然a是排好序的，a[start...mid]应该都比number小，所以mustbe(mid+1,end,number) */
                            start = mid + 1;
            /*维护了mustbe(start,endmnumber) */
                    else if (a[mid] > number)
            /* 既然a是排好序的，a[mid..end]应该都比number大，所以mustbe(start, mid-1, number) */
                            end = mid -1;
            /* 维护了mustbe(start, end, number) */
                    else
            /* a[mid] == number，说明找到了 */
                            return mid;
            }
            /*
            * mustbe(start, end, number)一直被循环维护着，到这里应该仍然成立，
            * 在a[start..end]范围之外一定不存在number，
            *  * 但现在a[start..end]是空序列，在这个范围之外的正是整个数组a，因此整
            *  个数组a中都不存在number
            *   */
            return -1;
    }

注意这个算法有一个非常重要的前提－－a是排好序的。缺了这个前提，“如果a\[mid\] < number，那么a\[start..mid\]应该都比number小”这一步推理就不能成立，这个函数就不能正确地完成查找。从更普遍的意义上说，函数的调用者（Caller）和函数的实现者（Callee，被调用者）之间订立了一个契约（Contract），在调用函数之前，Caller要为Callee提供某些条件，比如确保a是排好序的，确保a\[start..end\]都是有效的数组元素而没有访问越界，这称为Precondition，然后Callee对一些Invariant进行维护（Maintenance），这些Invariant保证了Callee在函数返回时能够对Caller尽到某些义务，比如确保“如果number在数组a中存在，一定能找出来并返回它的位置，如果number在数组a中不存在，一定能返回-1”，这称为Postcondition。如果每个函数的文档都非常清楚地记录了Precondition、Maintenance和Postcondition是什么，那么每个函数都可以独立编写和测试，整个系统就会易于维护。这种编程思想是由Eiffel语言的设计者Bertrand Meyer提出来的，称为Designby Contract（DbC）。

测试一个函数是否正确需要把Precondition、Maintenance和Postcondition这三方面都测试到，比如binarysearch这个函数，即使它写得非常正确，既维护了Invariant也保证了Postcondition，如果调用它的Caller没有保证Precondition，最后的结果也还是错的。我们编写几个测试用的Predicate函数，然后把相关的测试插入到binarysearch函数中：

### 带有测试代码的折半查找 ###

#include <stdio.h>
    #include <assert.h>
    #define LEN 8
    
    int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
    
    int is_sorted(void)
    {
             int i;
             for (i = 1; i < LEN; i++)
             if (a[i-1] > a[i])
             return 0;
             return 1;
    }
    
    int mustbe(int start, int end, int number)
    {
             int i;
             for (i = 0; i < start; i++)
             if (a[i] == number)
             return 0;
             for (i = end+1; i < LEN; i++)
             if (a[i] == number)
             return 0;
             return 1;
    }
    
    int contains(int n)
    {
             int i;
             for (i = 0; i < LEN; i++)
             if (a[i] == n)
             return 1;
             return 0;
    }
    
    int binarysearch(int number)
    {
             int mid, start = 0, end = LEN - 1;
             assert(is_sorted()); /* Precondition */
             while (start <= end) {
             assert(mustbe(start, end, number)); /* Maintenance */
             mid = (start + end) / 2;
             if (a[mid] < number)
             start = mid + 1;
             else if (a[mid] > number)
             end = mid - 1;
             else {
             assert(mid >= start && mid <= end && a[mid] == number); /* Postcondition 1 */
             return mid;
             }
     }

assert是头文件assert.h中的一个宏定义，执行到assert(is\_sorted())这句时，如果is\_sorted()返回值为真，则当什么事都没发生过，继续往下执行，如果is\_sorted()返回值为假（例如把数组的排列顺序改一改），则报错退出程序：

main: main.c:33: binarysearch: Assertion `is_sorted()' failed.
    Aborted

在代码中适当的地方使用断言（Assertion）可以有效地帮助我们测试程序。也许有人会问：我们用几个测试函数来测试binarysearch，那么这几个测试函数又用什么来测试呢？在实际工作中我们要测试的代码绝不会像binarysearch这么简单，而我们编写的测试函数往往都很简单，比较容易保证正确性，也就是用简单的、不容易出错的代码去测试复杂的、容易出错的代码。  
测试代码只在开发和调试时有用，如果正式发布（Release）的软件也要运行这些测试代码就会严重影响性能了，如果在包含assert.h之前定义一个NDEBUG宏（表示No Debug），就可以禁用assert.h中的assert宏定义，这样代码中的所有assert测试都不起作用了：

#define NDEBUG
    #include <stdio.h>
    #include <assert.h>
    ...

注意NDEBUG和我们以前使用的宏定义有点不同，例如\#define N 20将N定义为20，在预处理时把代码中所有的标识符N替换成20，而\#define NDEBUG把NDEBUG定义为空，在预处理时把代码中所有的标识符NDEBUG替换成空。这样的宏定义主要是为了用\#ifdef等预处理指示测试它定义过没有，而不是为了做替换，所以定义成什么值都无所谓，一般定义成空就足够了。  
还有另一种办法，不必修改源文件，在编译命令行加上选项-DNDEBUG就相当于在源文件开头定义  
了NDEBUG宏。