本文主要是介绍【王道数据结构】【chapter7查找】【P285t4】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
写出折半查找的递归算法。初始调用时，low为1，high为ST.length（下面的实现大体是相同的，就是没有进行封装）
#include <iostream>
#include <time.h>
#include<stdlib.h>
void binary_search(int * a,int left,int right,int search,int &position)
{if (left>right) return;int mid=(left+right)/2;if(a[mid]==search) {position=mid;return;}else if(a[mid]>search){binary_search(a,left,mid-1,search,position);}else{binary_search(a,mid+1,right,search,position);}}
int main() {srand(time(nullptr));int*data= (int *)(malloc(sizeof (int)*11));int tmp=0;for(int i=1;i<11;i++) {tmp=tmp+rand()%3+1;data[i]=tmp;}for(int i=1;i<11;i++){printf("%3d",data[i]);}puts("");int position=-1;binary_search(data,0,9,data[8],position);if(position!=-1)printf("the position is %3d\n",position);else printf("the number does not exit\n");position=-1;binary_search(data,0,9,7,position);if(position!=-1)printf("the position is %3d\n",position);else printf("the number does not exit\n");return 0;
}
第一个测试用例是一定可以查找到的，第二个不一定查找得到
这篇关于【王道数据结构】【chapter7查找】【P285t4】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
