利用折半查找算法在一个有序表中插入一个元素,并保持表 的有序性的代码
时间: 2024-05-08 18:22:23 浏览: 13
假设有序表已经存储在数组中,可以按照如下步骤进行折半查找和插入操作:
```C++
void insert(int arr[], int n, int x) {
int left = 0, right = n - 1;
while (left <= right) { // 折半查找
int mid = (left + right) / 2;
if (arr[mid] == x) {
return; // 如果元素已存在,则直接返回
} else if (arr[mid] < x) {
left = mid + 1; // 在右半部分查找
} else {
right = mid - 1; // 在左半部分查找
}
}
// 如果元素不存在,则将其插入到有序表中
for (int i = n - 1; i >= left; i--) {
arr[i + 1] = arr[i]; // 将后面的元素后移一位
}
arr[left] = x; // 插入元素
}
```
其中,参数 `arr` 表示有序表所在的数组,`n` 表示有序表中元素的数量,`x` 表示要插入的元素。在折半查找时,如果找到了元素,则直接返回;否则,根据当前元素与目标元素的大小关系,更新左右边界,直到找到插入位置为止。最后,将插入位置后面的元素都后移一位,腾出位置插入新元素。
相关问题
在有序表中利用折半查找查找关键字并输出查找位置c++完整代码
下面是一个示例代码,实现了在有序表中利用折半查找查找关键字并输出查找位置。
```c++
#include <iostream>
using namespace std;
// 有序表折半查找
int binarySearch(int arr[], int len, int key)
{
int low = 0, high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1; // 没有找到
}
int main()
{
int arr[] = {1, 3, 5, 7, 9};
int len = sizeof(arr) / sizeof(int);
int key = 7;
int pos = binarySearch(arr, len, key);
if (pos == -1) {
cout << "没有找到" << endl;
} else {
cout << "找到了,位置是:" << pos << endl;
}
return 0;
}
```
上述代码中,binarySearch 函数实现了有序表的折半查找。该函数接受三个参数:有序数组 arr,数组长度 len,以及要查找的关键字 key。函数返回值为 int 类型,表示查找到的关键字在数组中的位置,如果没有找到则返回 -1。在主函数中,我们定义了一个有序数组 arr,并调用 binarySearch 函数查找关键字 7 在数组中的位置。最终输出查找结果。
在有序表中利用折半查找查找关键字并输出查找位置
折半查找(二分查找)是一种在有序表中查找关键字的算法,其基本思想是每次将查找区间缩小一半,直到找到目标元素或者区间为空为止。
假设我们要在一个有序表arr中查找关键字key,初始时查找区间为整个表,即[0, n-1],其中n为表中元素个数。具体的查找过程如下:
1. 将查找区间的下标范围[left, right]初始化为[0, n-1]。
2. 计算区间中间位置mid,即mid = (left + right) / 2。
3. 如果arr[mid]等于key,则查找成功,返回mid。
4. 如果arr[mid]大于key,则说明key可能在左半边,将查找区间缩小为[left, mid-1]。
5. 如果arr[mid]小于key,则说明key可能在右半边,将查找区间缩小为[mid+1, right]。
6. 重复步骤2~5,直到找到目标元素或者区间为空为止。
下面是一个示例代码实现:
```python
def binary_search(arr, key):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == key:
return mid
elif arr[mid] > key:
right = mid - 1
else:
left = mid + 1
return -1 # 没有找到目标元素
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
key = 5
pos = binary_search(arr, key)
print("关键字位置:", pos)
```
输出结果为:
```
关键字位置: 4
```
说明在有序表arr中,关键字5位于下标为4的位置。