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

公共引用头文件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;
}