用二分查找法没找到时的平均查找长度
时间: 2023-06-19 22:06:32 浏览: 49
在二分查找中,如果要查找的元素不在已排序的数组中,则查找不成功。此时平均查找长度(ASL)取决于该元素应该出现的位置。如果该元素应该出现在数组的中心,则平均查找长度最小,为1。如果该元素应该出现在数组的两端,则平均查找长度最大,为log2(n)+1,其中n是数组的长度。
因此,如果在二分查找中未找到元素,则平均查找长度的期望值为(log2(n)+1)/2,其中n是数组的长度。换句话说,如果要查找的元素不在数组中,则平均需要查找数组的一半左右的元素。
相关问题
二分查找法
二分查找,也称为折半查找,是一种在有序数组中查找特定元素的搜索算法。它的工作原理是将数组分成两半,然后确定要查找的元素可能存在于哪一半,然后继续在该半中查找,直到找到要查找的元素或者确定它不存在为止。
具体实现步骤如下:
1.确定数组的左右边界,分别为left和right。初始时,left为0,right为数组长度减1。
2.计算中间元素的索引mid,mid等于left和right之和除以2。
3.比较要查找的元素与中间元素的值。如果相等,返回mid。如果要查找的元素小于中间元素的值,则在左半边继续查找,更新right为mid-1;如果要查找的元素大于中间元素的值,则在右半边继续查找,更新left为mid+1。
4.重复执行第二步和第三步,直到找到要查找的元素或者确定它不存在为止。
下面是一个简单的Python实现:
```python
def binary_search(arr, left, right, target):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, left, mid-1, target)
else:
return binary_search(arr, mid+1, right, target)
```
其中,arr为要查找的有序数组,left和right为数组的左右边界,target为要查找的元素。如果找到了要查找的元素,则返回它在数组中的索引,否则返回-1。
用c/c++距离二分查找法
距离二分查找法(又称为二分答案)可以用 C/C++ 实现,具体实现代码如下:
```c++
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-7; // 设置精度
int n; // 数组大小
double l, r; // 二分查找区间
double a[100005]; // 存储数据
bool check(double x) {
double sum = 0;
for (int i = 0; i < n; i++) {
sum += floor(a[i] / x); // 计算每个元素能够取到的整数个数
}
return sum >= l; // 判断是否满足要求
}
int main() {
cin >> n >> l;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
l = ceil(l); // 对于整数二分,需要向上取整
r = *max_element(a, a + n); // 取出数组中的最大元素,作为二分区间右端点
while (r - l > eps) { // 当区间长度小于精度时,停止二分
double mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
printf("%.2f\n", floor(r * 100) / 100); // 输出最终结果,保留两位小数
return 0;
}
```
上述代码实现了一个简单的距离二分查找算法,其中 `check` 函数用于判断当前二分答案是否满足要求。在本例中,我们需要计算数组中所有元素能够取到的整数个数之和,如果大于等于给定的 `l`,则说明当前答案可行。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)