C基础算法之二分法查找

时间:2021-06-01 22:09:22

算法:当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。 基本思想:假设数据是按升序排序的,对于给定值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方法。

 

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