C基础算法之二分法查找

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

二分法查找在针对大量有序排列的情况下发挥出很优越的效率，这里以最具规律性的数组为例，代码如下：

示例代码：

/* binarysearch2.c --- 
 * 
 * Filename: binarysearch2.c
 * Description: 用循环方式和递归两种方式 实现二分法查找过程
 * Author: magc
 * Maintainer: 
 * Created: 三  7月 25 23:26:52 2012 (+0800)
 * Version: 
 * Last-Updated: 四  7月 26 00:22:37 2012 (+0800)
 *           By: magc
 *     Update #: 74
 * URL: 
 * Keywords: 递归 二分法查找
 * Compatibility: 
 * 
 */

/* Commentary: 
 * 
 * 
 * 
 */

/* Change Log:
 * 添加循环方式和递归方式
 * 
 */

/* Code: */
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <string.h>
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>

int binarysearch(int arr[],int len,int key);
int binarysearch2(int array[],int key,int low,int high);

    
int main(int argc, char * argv[])
{
    int array[] = {3,5,6,7,11,22,44,47 };
    int i;
    printf("请参照下列数组，输入你要查找的目标：\n {");
    int len = sizeof(array)/sizeof(int);
    
    for (i = 0; i < len; i++) {

        printf("%d,",array[i]);
        
    }
    printf("}:\n");
    int dest;
    scanf("%d",&dest);
    int res = binarysearch(array,len,dest);
    printf("1. res = %d\n",res);

    int res2 = binarysearch2(array,dest,0,len - 1);
    printf("2. res = %d\n",res2);

    
}
/**************************************************************************
函数名称：用循环实现二分法查找过程,
功能描述：
输入参数：
返   回：返回目标值在数组中的下标
**************************************************************************/


int binarysearch(int arr[],int len,int key)
{

    int high,low;
    high = len - 1;//假设数组是从小到大排列的
    low = 0;
    int midle = len/2;
    
    while(high >= low)
        {
            midle = (high + low)/2;
            
           if(arr[midle] == key)
               return midle;
           if(arr[midle] > key)
               high = midle - 1;         //前提是假设数组是从小到大排序，否则不确定是该加1还是减1
           else if(arr[midle] < key )
               low = midle + 1;
        }
    return (-1);
    
}
/**************************************************************************
函数名称：用递归实现二分法查找
功能描述：
输入参数：
返   回：
**************************************************************************/
int binarysearch2(int array[],int key,int low,int high)
{

    if (low >= high)
        return (-1);

    int midle = (low + high)/2;
    if(array[midle] == key)
        return midle;
    if(midle == high || midle == low) //此时，只剩下了下标为high和low的两个数，确定另一个数不是key后，就确定查找完毕，并且未找到目标值
        {
            if(array[high] == key)
                return high;
            else if(array[low] == key)
                return low;
            else
                return (-1);            
        }

    else if(array[midle] > key)
        return binarysearch2(array,key,low,midle);  //由于不确定排序方向，所以此处只能用midle值，而不能加1或减1
    else if(array[midle] < key)                    //当中间值小于目标值时，在high的一侧继续查找，low变到midle位置上
        return binarysearch2(array,key,midle,high);
}


/* binarysearch2.c ends here */

在GCC下编译运行结果如下：

C基础算法之二分法查找

注：

1）在第一个方法中，

要体会到二分法查找的思路，设置high和low参数的好处是，不论数组是从大到小还是从小到大排列，此函数皆适用。

注意把握此例中high和low的变更过程，特别是边界，当high和low相邻时，取到的midle值总是二者之一，若继续查找，便进入死循环状态，此时确定没有目标值，退出查找

3）理解递归的思路，凡可以递归的问题，一般用循环也能实现（反之不然），如binarysearch2方法。

在整理思路时，要准确把握变与不变因素，进而实现

秒客网

C基础算法之二分法查找

相关文章