• 二分查找

二分查找

#include <stdio.h>

#include <stdio.h>
int binary_search(int key,int a[],int n) //自定义函数binary_search()
{
    int low,high,mid,count=0,count1=0;
    low=0;
    high=n-1;
    while(low<=high)    //査找范围不为0时执行循环体语句
    {
        count++;    //count记录査找次数
        mid=(low+high)/2;    //求中间位置
        if(key<a[mid])    //key小于中间值时
            high=mid-1;    //确定左子表范围
        else if(key>a[mid])    //key 大于中间值时
            low=mid+1;    //确定右子表范围
        else if(key==a[mid])    //当key等于中间值时，证明查找成功
        {
            printf("查找成功!\n 查找 %d 次!a[%d]=%d",count,mid,key);    //输出査找次数及所査找元素在数组中的位置
            count1++;    //count1记录查找成功次数
            break;
        }
    }
    if(count1==0)    //判断是否查找失敗
        printf("查找失敗!");    //査找失敗输出no found
    return 0;
}


int main()
{
	int a[] ={1,2,5,6,7};
	binary_search(7,a,5);
	
   /* 我的第一个 C 程序 */
   printf("Hello, World! \n");
   
   return 0;
} 

#include <stdio.h>

/** 
 * 递归方法实现二分查找法. 
 * @param Array数组 
 * @param low 数组第一位置 
 * @param high 最高 
 * @param key 要查找的值. 
 * @return 返回值. 
 */  
int BinSearch(int Array[],int low,int high,int key)  
{  
    if (low<=high)  
    {  
        int mid = (low+high)/2;  
        if(key == Array[mid])  
            return mid;  
        else if(key<Array[mid])  
            //移动low和high  
            return BinSearch(Array,low,mid-1,key);  
        else if(key>Array[mid])  
            return BinSearch(Array,mid+1,high,key);  
    }  
    else  
        return -1;  
}  


int main()
{
	
	int a[] ={1,2,5,6,7};
	int r = BinSearch(a,0,5,7);
   printf("%d",r);
	/* 我的第一个 C 程序 */
   printf("Hello, World! \n");
   
   return 0;
} 

因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：
一次二分剩下：n/2
两次二分剩下：n/2/2 = n/4
…
m次二分剩下：n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果，即
n/(2^m)=1
所以由上式可得 ： 2^m=n
进而可求出时间复杂度为： log2(n)

参考：
https://blog.csdn.net/u011489043/article/details/69357726?utm_source=blogxgwz9
https://www.cnblogs.com/csniper/p/5751521.html
http://c.biancheng.net/view/536.html