二分查找

绝地灬酷狼 2022-05-12 01:40 19阅读 0赞

//二分查找  
/\*  
递归算法  
int searchB1(int A\[\], int low, int high, int data);  
非递归算法  
int searchB2(int A\[\], int len, int data);  
\*/  
\#include<stdio.h>  
\#include<string.h>  
\#define Len 25  
//递归算法  
int searchB1(int A\[\], int low, int high, int data);  
//非递归算法  
int searchB2(int A\[\], int len, int data);  
void main()  
\{  
int i;  
int len = 0;  
int data; //要查找的字符  
int result = 0;  
int A\[\] = \{1,2,3,4,5,6,7,8,9\};  
len = sizeof(A) / sizeof(int);  
printf("output the primary data:");  
for(i = 0; i < len; i++)  
\{  
if( i % 5 == 0)  
printf("\\n");  
printf("A\[%d\]:%d\\t",i,A\[i\]);  
\}  
printf("\\nintput the searched char:");  
scanf("%d",&data);

result = searchB1(A,0,len-1,data);  
printf("recursion search.\\n");  
if( result == -1 )  
\{  
printf("Sorry,no this char.\\n");  
\}  
else  
\{  
printf("the char is %d.\\n",A\[result\]);  
printf("the index of the char in Array is %d.\\n",result);  
\}

result = searchB2(A,len,data);  
printf("unrecursion search.\\n");  
if( result == -1 )  
\{  
printf("Sorry,no this char.\\n");  
\}  
else  
\{  
printf("the char is %d.\\n",A\[result\]);  
printf("the index of the char in Array is %d.\\n",result);  
\}  
  
\}

//非递归算法  
int searchB2(int A\[\], int len, int data)  
\{  
int low = 0;  
int high = len - 1;  
int mid = 0;  
while( low <= high )  
\{  
mid = ( low + high ) / 2;  
if( A\[mid\] == data )  
\{  
return mid;  
\}  
else if( A\[mid\] < data )  
\{  
low = mid + 1;  
\}  
else  
\{  
high = mid - 1;  
\}  
\}  
//没有返回-1  
return -1;  
\}

int searchB1(int A\[\], int low, int high, int data)  
\{  
if( low <= high )  
\{  
int mid = ( low + high ) / 2; //low+((high-low)/2)可能更严谨  
if( A\[mid\] == data )  
\{  
return mid;  
\}  
else if( A\[mid\] < data )  
\{  
low = mid + 1;  
return searchB1(A,low,high,data);  
\}  
else  
\{  
high = mid - 1;  
return searchB1(A,low,high,data);  
\}  
\}  
else  
\{ //没有返回-1  
return -1;  
\}  
  
\}

![1355021331_5463.jpg][]

/\*博主寄语：如若发现错误，望指出，谢谢\*/

[1355021331_5463.jpg]: https://img-my.csdn.net/uploads/201212/09/1355021331_5463.jpg