二分查找原理

Source Code

#include<stdio.h>

void Pop(int * a, int n);
int BinSearch(int * a, int n, int x);

int main(int argc, char * argv[]) {
	int a [] = {1, 4, 7, 9, 23, 45, 5, 6, 67, 6, 8, 8, 76, 8, 7, 98, 7};
	int ret = 0;
	Pop(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
		printf("%d  ", a[i]);
	}
	printf("\n");
	int x = 0;
	scanf("%d",&x); 
	ret = BinSearch(a,  sizeof(a) / sizeof(int), x);
    if(ret != -1){
		printf("%d  %d", ret, a[ret]);
	} else return ret; 
	
	return 0;
}

void Pop(int *a, int n) {
	int swap;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i ; j++) {
			if (a[i] < a[j]) {
				swap = a[i];
				a[i] = a[j];
				a[j] = swap;
			}
		}
	}
}

int BinSearch(int * a, int n, int x) {
	int low = 0;
	int high = n - 1;
	int mid = 0;
	while (low <= high) {
		mid = ((low + high) >> 1);
		if(a[mid] > x){
			high = mid - 1;
		} else if(a[mid] < x){
			low = mid + 1 ;
		} else {
			printf("In Bin Search: Index:%d\n",mid);
			return mid;
		} 
	}
	return -1;
}

二分查找原理

使用条件

• 线性表中的记录必须关键码有序
• 必须采用顺序存储

基本思想

• 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，知道查找成功，或所查找的区域无记录，查找失败。