有序表的折半查找算法。
时间: 2023-12-15 18:32:35 浏览: 66
C++中有序表的折半查找算法,也称为二分查找算法,是一种高效的查找方法。它的基本思想是:将有序表分成两部分,取中间位置的元素与查找关键字进行比较,如果相等,则查找成功;否则根据中间位置元素与查找关键字的大小关系确定下一步查找哪个子表,重复以上过程,直到查找成功或查找失败为止。
下面是C++中有序表的折半查找算法的代码实现:
```c++
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
其中,arr为有序表,left和right分别为有序表的左右边界,target为要查找的关键字。函数返回值为查找到的元素在有序表中的下标,如果查找失败则返回-1。
需要注意的是,使用折半查找算法的前提是有序表必须是有序的,否则无法保证查找结果的正确性。
相关问题
有序表的折半查找算法
有序表的折半查找算法,也称为二分查找算法。它是一种高效的查找算法,适用于已经按照升序(或降序)排列好的有序表。
折半查找的基本思想是:首先确定待查找区间的中间位置mid,然后将要查找的值与中间位置的值进行比较。如果待查找值等于中间位置的值,则查找成功;如果待查找值小于中间位置的值,则在左半部分继续查找;如果待查找值大于中间位置的值,则在右半部分继续查找。重复以上步骤,直到找到待查找值或者确定该值不存在。
以下是折半查找算法的伪代码:
```
binarySearch(array, target):
left = 0
right = length(array) - 1
while left <= right:
mid = (left + right) // 2
if array[mid] == target:
return mid
if array[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
其中,array是有序表(数组), target是待查找的值。算法使用两个指针left和right来表示待查找区间的左右边界。
该算法的时间复杂度为O(logn),其中n是有序表的长度。因为每次比较都将待查找区间缩小一半,所以算法的查找效率非常高。但是,折半查找算法要求有序表是静态的,即不会频繁插入、删除元素,否则需要进行排序操作。
实现基于有序顺序表的折半查找算法
折半查找算法,也称为二分查找算法,是一种常用的查找算法。它要求查找表是有序的,根据查找表中间位置的关键字与待查关键字的比较结果,将查找区间缩小为表的一半,直到找到待查元素或查找区间为空为止。
基于有序顺序表的折半查找算法的实现步骤如下:
1. 定义一个有序顺序表,包含元素的关键字按照从小到大的顺序排列。
2. 定义待查元素的关键字 key。
3. 定义查找区间的左边界 left 和右边界 right,初始时 left=0,right=n-1,其中 n 是顺序表的长度。
4. 当 left<=right 时,执行以下步骤:
(1) 计算中间位置 mid = (left + right) / 2。
(2) 如果中间位置的关键字等于待查关键字 key,则返回 mid。
(3) 如果中间位置的关键字大于待查关键字 key,则在左半区间继续查找,将右边界 right 更新为 mid-1。
(4) 如果中间位置的关键字小于待查关键字 key,则在右半区间继续查找,将左边界 left 更新为 mid+1。
5. 如果查找区间为空,即 left>right,则返回查找失败。
以下是基于有序顺序表的折半查找算法的 C++ 实现:
```cpp
int binarySearch(int a[], int n, int key) {
int left = 0, right = n-1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == key) return mid;
else if (a[mid] > key) right = mid - 1;
else left = mid + 1;
}
return -1; // 查找失败
}
```