北京软件公司招聘信息查询_宁波人流医院哪家好_百度搜索资源平台_网站怎么做出来的

1.在递增有序的表中，写出折半查找的递归算法。初始调用时，low=1,high=ST.lengh。

思想：先判断是否为表空；然后进行划分左右子表，判断要找的是比中间值大还是小，对应递归左或者右表。

代码：

typedef struct{EleType *elem;int length
}SSTable; 
int BinSearch(SSTable ST,int key,int low,int high){if(low>high) return -1;//表空 int mid=(low+high)/2;//取中间位置if(key>SSTable.elem[mid]){return BinSearch(ST,key,mid+1,high);//比中间位置大，右边 } else if (key<SSTable.elem[mid]){return BinSearch(ST,key,low,mid-1);//比中间位置小，左边 }else{return mid;//找到了 }
} 

时间复杂度O（logn)；空间复杂度O（1） 

2.写一个非递归算法，该算法在按照值严格递增排序的顺序表A[1....n]中采用折半查找不小于item的最小元素。若存在这样的元素，则算法给出该最小元素中的位置，否则给出信息为0。

思想：

表中元素小于2时，结束查找。当前元素大于等于待查找元素时，都去左表找，否则都去右表找。

如果找到了item，则item右侧元素为不小于item的最小元素。否则查找失败

例子：

待查找表：5 10 15 20 25；带差找元素：7。返回high=2，元素为10。

代码：

typedef struct{EleType *elem;int length
}SSTable; 
int BinSearch(SSTable s,int key){int low=0,high=s.length;while(high-low>1){int mid=(low+high)/2;if(s.elem[mid]>=key){high=mid;}else{low=mid;}}return (s.elem[high]>=key)?high:0;
} 

时间复杂度O（logn)；空间复杂度O（1）