数据结构基础_二分法查找

公共引用头文件common.h

 

#include <stdio.h>
#include <stdlib.h>


/**
*
* @param p   待申请内存的指针
* @param s   申请内存大小
*/
#define MALLOC(p,s) \
if(!((p) = malloc(s)) ){\
	fprintf(stderr, "Insufficient memory");\
	exit(EXIT_FAILURE);\
}

/**
* 交换两个数  宏定义方式
* @param x  交换数1
* @param y  交换数2
* @param t  临时变量
*/
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))

void swap(int *x,int *y){
	int temp = *x;
	*x = *y;
	*y =temp;
}


#define COMPARE(x, y) ( ((x) < (y)) ? -1 : ((x) == y) ? 0 : 1 )

int compare(int x,int y){
	if(x < y){
		return -1;
	}else if(x == y){
		return 0;
	}else{
		return 1;
	}
}

1.  一般方法

 

#include "common.h"

int binSearch(int list[], int searchNum, int left, int right){
	int middle;
	while(left <= right){
		middle = (left + right) / 2;
		switch(COMPARE(list[middle], searchNum)){
		case -1:
			left = middle + 1;
			break;
		case 0:
			return middle;
		case 1:
			right = middle - 1;
			break;
		}
	}
	return -1;
}


int main(){
	int list[] = {10,20,40,50,36,40,50,20};
	int left = 0;
	int right = 8;
	int i;
	int searchNum = 20;
	int position;

	printf("目标数组为\n");
	for(i = 0; i < 8; i++) {
		printf("%d ", list[i]);
	}
	position = binSearch(list, searchNum, left, right);
	printf("\n%d在数组中的位置为第%d个", searchNum, position + 1);
	return 0;
}

2.  递归方法

int binSearch2(int list[], int searchNum, int left, int right){
	int middle;
	while(left <= right){
		middle = (left + right) / 2;
		switch(COMPARE(list[middle], searchNum)){
		case -1:
			return binSearch2(list, searchNum, middle + 1, right);
		case 0:
			return middle;
		case 1:
            return binSearch2(list, searchNum, left, right - 1);
		}
	}
	return -1;
}