在有序表中利用顺序查找查找关键字并输出查找位置
时间: 2023-07-18 22:03:12 浏览: 47
顺序查找是一种基础的查找算法,适用于数据量较小或无序的情况。在有序表中进行顺序查找时,可以利用表的有序性进行优化。
具体实现步骤如下:
1. 从有序表的第一个元素开始依次比较,如果当前元素等于待查找的关键字,则返回当前位置。
2. 如果当前元素大于待查找的关键字,则说明待查找的元素不存在于有序表中,返回-1。
3. 如果当前元素小于待查找的关键字,则继续向后查找,直到找到目标元素或查找完整个有序表。
以下是一个具体的示例程序:
```c++
#include <iostream>
using namespace std;
int search(int arr[], int len, int key) {
int pos = -1;
for (int i = 0; i < len; i++) {
if (arr[i] == key) {
pos = i;
break;
}
if (arr[i] > key) {
break;
}
}
return pos;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int len = sizeof(arr) / sizeof(arr[0]);
int key = 7;
int pos = search(arr, len, key);
if (pos != -1) {
cout << "The position of " << key << " is " << pos << endl;
} else {
cout << key << " is not found!" << endl;
}
return 0;
}
```
输出结果为:
```
The position of 7 is 3
```
在这个示例程序中,我们首先定义了一个search函数,它接收一个有序表arr,表长度len和待查找的关键字key作为参数,并返回关键字在表中的位置。在函数内部,我们使用for循环逐个比较表中的元素,如果找到了目标元素,则返回它的位置;如果当前元素已经大于目标元素,则说明目标元素不存在于表中,退出查找并返回-1。
在主函数中,我们定义了一个有序表arr,并调用search函数查找关键字7在表中的位置。最终输出结果为3,表示7位于有序表的第4个位置。