改进的二分查找

谁借莪１个温暖的怀抱￠ 2022-05-12 01:48 137阅读 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,3,3,3,3,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 )  
\{  
if(low == high )  
return mid;  
else  
\{  
if( A\[mid - 1\] == data )  
\{//A\[mid\]和A\[mid-1\]都等于data,则继续查找  
high = mid - 1;  
\}  
else  
\{  
return mid;  
\}  
\}  
\}  
else if( A\[mid\] < data )  
\{  
low = mid + 1;  
\}  
else  
\{  
high = mid - 1;  
\}  
\}//end while  
//没有返回-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 )  
\{  
if(low == high )  
return mid;  
else  
\{  
if( A\[mid - 1\] == data )  
\{//A\[mid\]和A\[mid-1\]都等于data,则继续查找  
high = mid - 1;  
return searchB1(A,low,high,data);  
\}  
else  
\{  
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;  
\}  
  
\}

![1355021490_2268.jpg][]

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

[1355021490_2268.jpg]: https://img-my.csdn.net/uploads/201212/09/1355021490_2268.jpg