// 折半查找 int binary_search(int ticket_num) { int left = 0, right = count-1; while(left <= right) { int mid = (left + right) / 2; if (passengers[mid].ticket_num == ticket_num) { return mid; } else if (passengers[mid].ticket_num > ticket_num) { right = mid - 1; } else { left = mid + 1; } } return -1; }
时间: 2024-03-29 08:41:00 浏览: 21
这段代码实现了一个折半查找的算法。折半查找也被称为二分查找,是一种在有序数组中查找某一特定元素的搜索算法。它的基本思想是将查找区间分为两部分,通过比较中间元素和目标元素的大小,缩小查找范围,直到找到目标元素或者查找区间为空。
在这段代码中,我们定义了一个函数 `binary_search`,它接受一个参数 `ticket_num`,表示要查找的车票编号。函数中首先定义了两个变量 `left` 和 `right`,分别表示查找区间的左右边界。初始时,左边界为0,右边界为数组中最后一个元素的下标。
接下来,我们使用一个循环来不断缩小查找区间的范围,直到找到目标元素或者查找区间为空。在每一次循环中,我们计算当前查找区间的中间位置 `mid`,然后比较中间元素的车票编号和目标车票编号的大小。如果相等,说明找到了目标元素,直接返回当前位置 `mid`。如果中间元素的车票编号大于目标车票编号,说明目标元素在左半部分,将右边界缩小到 `mid-1`。否则,目标元素在右半部分,将左边界扩大到 `mid+1`。
最后,如果循环结束仍然没有找到目标元素,说明目标元素不存在于数组中,返回 -1 表示查找失败。
相关问题
#include <iostream> #include <algorithm> using namespace std; // 顺序查找 int sequential_search(int* list, int size, int key) { int count = 0; for (int i = 0; i < size; i++) { count++; if (list[i] == key) { cout << "找到元素在 " << i+1 << ".比较次数:" << count << endl; return i; } } cout << "找不到元素。比较次数: " << count << endl; return -1; } // 折半查找 int binary_search(int* list, int left, int right, int key) { int count = 0; while (left <= right) { count++; int mid = (left + right) / 2; if (list[mid] == key) { cout << "找到元素在 " << mid+1 << ".比较次数:" << count << endl; return mid; } else if (list[mid] < key) { left = mid + 1; } else { right = mid - 1; } } cout << "找不到元素。比较次数: " << count << endl; return -1; } int main() { // 测试数据 int list1[] = {3, 6, 2, 10, 1, 8, 5, 7, 4, 9}; int list2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int list3[] = {6, 14, 20, 25, 39, 59, 67, 78, 89, 96, 123}; int key1 = 5, key2 = 9, key3 = 9, key4 = 96, key5 = 97; // 顺序查找无序表 cout << "1\n"; sequential_search(list1, sizeof(list1)/sizeof(int), key1); // 顺序查找有序表 cout << "2\n"; sequential_search(list2, sizeof(list2)/sizeof(int), key2); // 折半查找有序表 cout << "3\n"; binary_search(list3, 0, sizeof(list3)/sizeof(int)-1, key3); // 顺序查找无序表 cout << "4\n"; sequential_search(list3, sizeof(list3)/sizeof(int), key4); sequential_search(list3, sizeof(list3)/sizeof(int), key5); // 折半查找有序表 cout << "5\n"; binary_search(list3, 0, sizeof(list3)/sizeof(int)-1, key4); binary_search(list3, 0, sizeof(list3)/sizeof(int)-1, key5); return 0; }
这是一段 C++ 代码,其中实现了顺序查找和折半查找两种查找算法。顺序查找是在无序表中按顺序逐个查找关键字,时间复杂度为 O(n);折半查找是在有序表中将表分成两半,每次将待查找的关键字与中间位置的关键字进行比较,从而缩小查找范围,时间复杂度为 O(log n)。代码中还定义了几个测试数据和关键字,可以用于测试两种算法的性能。
//折半查找算法,找不到返回0 int Search_Bin(SSTable &ST, int key) { //--------补充代码--Start------ //--------补充代码--End------- }
以下是折半查找算法的实现,如果找不到则返回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;
}
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)