二分（折半）查找算法练习

Time Limit: 1000 MS	Memory Limit: 32768 K

Total Submit: 404 (216 users)	Total Accepted: 230 (211 users)	Special Judge: No

Description

在一个有序表中利用二分法查找某个关键字是否存在。

Input

输入为多组数据，每组为两行数据，每组中第一行为建立查找的顺序表，第二行是要查找的关键字。

Output

若找到关键字，则输出关键字在表中的位置，否则输出0.

Sample Input

1 2 3 4 5
10
1 2 3 4 5
5
Sample Output

0
5
#include<stdio.h>
#include<stdlib.h>
typedef int elep;
#define maxn 1005
struct sq
{
    elep *p;
    elep length;
    elep size;
};
void insert(sq &l,int x)
{
    l.p[l.length+1]=x;//插入元素
    l.length++;//刷新表内元素个数
}
sq start()
{
    sq l;
    l.p=(int *)malloc(maxn*sizeof(elep));//开辟空间
    l.length=0;
    l.size=maxn;//设置最大容量
    return l;
}
int BinarySearch(sq l ,int n, int key){ 						//折半查找（二分）
	int low,high,mid;
	low=1;														//最低下标
	high=n;														//最高下标
	while(low<=high){
		mid=(low+high)/2;										//二分
		if(key<l.p[mid]){
			high=mid-1;
		}else if(key>l.p[mid]){
			low=mid+1;
		}else{
			return mid;
		}
	}
	return 0;
}
int main()
{
    sq l;
    int a,b;
    l=start();
    while(~scanf("%d",&a))
        {
            insert(l,a);
        if(getchar()=='\n') {
        scanf("%d",&b);
        printf("%d\n",BinarySearch(l,l.length,b));
    }}}

一、定义：

折半查找也称二分法查找，是一种在有序数组中查找某一特定元素的搜索算法。这种方法要求待查找的表顺序存储而且必须是有序的。

二、查找过程

首先计算表中间的位置，将表中间位置处的关键字与查找的关键字进行比较，如果相等，则查找成功；否则利用中间位置将表分为前、后两个子表，如果中间位置的关键字大于查找的关键字，则查找前子表，否则查找后子表。重复上面的过程，直到找到要查找的关键字为止，否则查找失败不存在此关键字。

例：对{2,5,6,9,17,23,54}中的17进行查找


如图，初始时先让low和high在数据集合的头和尾，中间位置为mid,low=0,high=6.所以mid=（0+6）/2=3，即3位置处，关键字为9不等于17，因为17>9//中间位置的关键字小于要查找的关键字，所以应该在后半子表中。接着再计算后半子表中的中间位置：此时low=mid+1,high=high,则mid=(4+6)/2=5，即5处的关键字为23,23不等于17,且17<23//中间位置的关键字大于要查找的关键字，所以应该在前半子表中，前半子表的中间位置为：此时low=low,high=mid-1,则mid=(4+4)/2=4,4处的关键字为17，查找成功结束。以此方法，如果查找的关键字在数据集合中不存在，会出现low>high。所以结束条件为low>high或者找到关键字为止.
a[mid]==key   return mid;//中间位置的关键字等于要查找的关键字
a[mid]<key    low = mid + 1;//中间位置的关键字小于要查找的关键字
a[mid]>key   high = mid - 1;//中间位置的关键字大于要查找的关键字

三、实现

方法一：非递归方法
#include<stdio.h>
#define N 7

int Search(int a[],int low,int high,int key){
	int mid;
	while(low<=high){
		mid = (low+high)/2;
		if(a[mid]==key){//查找到
			return mid;
		}else if(a[mid]<key){//中间位置的关键字小于要查找的关键字
			low = mid+1;
		}else{//中间位置的关键字大于要查找的关键字
			high = mid-1;
		}
	}
	return -1;
}


int main(void)
{
	int a[N]={2,5,6,9,17,23,54};
	int i,key;
	printf("请输入你要查找的值:");
	scanf("%d",&key);
	i = Search(a,0,N-1,key);
	printf("%d",i);
	return 0;
}

递归方法
#include<stdio.h>
#define N 7

int Search(int a[],int low,int high,int key){
	int mid;
	if(low>high){
		return -1;
	}else{
		mid = (low+high)/2;
		if(a[mid]==key){
			return mid;
		}else if(a[mid]<key){//中间位置的关键字小于要查找的关键字
			return Search(a,mid+1,high,key);
		}else{//中间位置的关键字大于要查找的关键字
			return Search(a,low,mid-1,key);
		}
	}
}


int main(void)
{
	int a[N]={2,5,6,9,17,23,54};
	int i,key;
	printf("请输入你要查找的值:");
	scanf("%d",&key);
	i = Search(a,0,N-1,key);
	printf("%d",i);
	return 0;
}

二分查找会生成一棵二叉查找树

时间复杂度o(lbn)

编写代码在一个整形有序数组中查找具体的某个数
我们如何在一个整形数组中找到某个具体的数呢？今天跟大家分享一个二分查找算法，二分查找又称折半查找。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功;否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

具体代码：
int main()
{
	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };//定义一个整形有序数组
	int key = 0;//我们要查找的数
	scanf_s("%d", &key);
	int left = 0;//数组做下标
	int right = sizeof(arr) / sizeof(arr[0]) - 1;//数组右下标
	while (left <= right)//当满足时，进入循环
	{
		int mid = (left + right) / 2;//求出中间数的下标
		if (arr[mid] < key)//key>arr[mid],说明key在中间数右边
		{
			left = mid + 1;//左下标加重新得到一个子表
		}
		else if (arr[mid]>key)//与上面相反
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标是：%d", mid);//找到的话,打印出下标
			break;
		}
	}
	if (left>right)//
	
	{
		printf("没找到");
	}
	return 0;
}

运行结果；





二分查找的优点是比较次数少，查找速度快，平均性能好，占用系统内存较少;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

我们可以利用有序这个特点，设计一些高效的算法。

例如：1.折半查找  2.斐波那契查找 3.插值查找
1.折半查找
实现思路
顾名思义，折半查找就是在一个查找范围内以中间点为关键字，与给定值进行比较，从而寻找下一个查找范围。随着查找范围的不断缩小，结果越逼近给定值。
书上的定义：先确定待查记录所在的范围，然后追捕缩小范围知道找到或者找不到该纪律为止。
代码
int Search_Bin(SSTable ST,int key)
{
//折半查找。查找num在顺序表ST中的位置
	//只适用于有序的顺序表
	int i,mid;
int low=1;
int high=ST.length-1;
	while(low<=high)
	{
		mid=(high+low)/2;
		if(ST.a[mid]==key)
			return mid;
		else
			if(ST.a[mid]>key)
				high=mid-1;
			else
				low=mid+1;
	}
	return 0;
}

性能分析
ASL= ((n+1)/n)log2(n+1)-1，当n较大时，ASL=log2(n+1)-1

折半查找的效率比顺序查找的高，但折半查找只适用于有序表，且限于顺序存储结构（对线性链表无法有效地进行折半查找）