C语言实现二分搜索算法

引言：

    这是我写的第一篇关于算法的文章，因为在计算机科学中，分治法的使用频率高，而且，分治法的思想简单“分而治之”，就是将一个难以直接解决的大问题，分割成一些规模较小的相同问题。但是思想虽然简单却是一种很重要的算法。下面是分治法求解的一个经典问题“二分搜索算法”。

题目：

    给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。

分析：

二分搜索算法（折半查找法）是运用分治策略的典型例子。

很显然此问题分解出的子问题相互独立，即在a[i]的前面或后面查找x是独立的子问题，因此满足分治法的适用条件

 实现：

#include <stdio.h>
int binarySearch(int a[], const int& x, int n)
{
    int left=0, right=n-1;
    while (left <= right)
    {
        int middle = (left+right)/2;
        if (x==a[middle])
        {
            return middle;
        }
        if (x > a[middle])
        {
            left = middle+1;
        }
        else
        {
            right = middle-1;
        }
    }
    return -1;
}
 
void main()
{
    int a[] = {1,3,5,7,11,14};
    printf("%d\n",binarySearch(a,7,6));
}
           

复杂度分析：

    时间：

每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。

注：影响算法时间代价的最主要因素是问题规模

分治法的补充：

    设计程序是的思维过程：

            实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。

            1、一定是先找到最小问题规模时的求解方法

            2、然后考虑随着问题规模增大时的求解方法

            3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。

      分治法适用的条件

            分治法所能解决的问题一般具有以下几个特征：

            1) 该问题的规模缩小到一定的程度就可以容易地解决

            2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

            3) 利用该问题分解出的子问题的解可以合并为该问题的解；

            4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

   注：如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，

         此时虽然也可用分治法，但一般用动态规划较好。

            第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

            第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备

            第三条特征，则可以考虑用贪心法或动态规划法。

            第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，

            此时虽然可用分治法，但一般用动态规划法较好。