//折半查找算法,找不到返回0 int Search_Bin(SSTable &ST, int key) { //--------补充代码--Start------ //--------补充代码--End------- }
时间: 2023-11-23 07:07:38 浏览: 55
以下是折半查找算法的实现,如果找不到则返回0:
```c++
int Search_Bin(SSTable &ST, int key)
{
int low = 1, high = ST.length, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (ST.R[mid].key == key)
{
return mid;
}
else if (ST.R[mid].key > key)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return 0;
}
```
相关问题
下列算法的功能为:采用折半方法进行关键字的查找,请将算法中缺失的语句按照顺序填入对应的空格。 结构定义: typedef int KeyType; typedef struct{ KeyType key; }ElemType; typedef struct { ElemType *elem; int length; } SSTable; 折半查找算法: int Search_Bin(SSTable &ST,KeyType key){ //在有序表ST中折半查找其关键字等于key的数据元素 //若找到,则函数值为该元素在表中的位置,否则为0 int low=1, high=ST.length,mid; while(low<=high){ ; // (1) if(EQ(key, )) // (2) return mid; else if(LT(key,ST.elem[mid].key)) ; // (3) else ; // (4) } return 0; }
折半查找算法:
int Search_Bin(SSTable &ST,KeyType key){
//在有序表ST中折半查找其关键字等于key的数据元素
//若找到,则函数值为该元素在表中的位置,否则为0
int low=1, high=ST.length,mid;
while(low<=high){
mid = (low+high)/2; // (1) 折半计算中间位置
if(EQ(key, ST.elem[mid].key)) // (2) 关键字与中间位置元素相等
return mid;
else if(LT(key,ST.elem[mid].key)) // (3) 关键字小于中间位置元素
high = mid-1;
else // (4) 关键字大于中间位置元素
low = mid+1;
}
return 0;
}
二分查找算法描述如下:intsearch_bin(sst st, kt key){ low=1 ; high=st. length;
二分查找算法也被称为折半查找算法,是一种常见的查找算法。其主要思想是在有序数组中查找某个元素时,先确定该元素在数组中可能出现的区间范围,然后每次取该范围的中间值与目标元素进行比较,不断缩小目标元素可能出现的范围。当目标元素与中间值相等时,查找成功,否则根据中间值与目标元素的大小关系调整区间范围,再进行下一次查找。
具体地,二分查找算法的描述如下:
输入:已经有序的数组sst,待查找的元素kt
输出:目标元素的下标或者-1(表示未找到)
1. 初始化low=1,high为数组长度
2. 当low<=high时,重复以下步骤:
- a. 取中间值mid=(low+high)/2
- b. 若中间值等于目标元素kt,则返回mid
- c. 若中间值大于目标元素kt,则缩小右边的区间范围,将high=mid-1
- d. 若中间值小于目标元素kt,则缩小左边的区间范围,将low=mid+1
3. 若未找到目标元素,则返回-1
二分查找算法的时间复杂度为O(logn),相比于线性查找算法具有更高的效率。同时,该算法只适用于有序数组,对于无序数组需要先进行排序操作。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)