2-3 设a[o:n-1]是已排好序的数组。请改写二分搜索算法,使得当搜索元素:不在组中时,返回小于x的最大元素位置i和大于x的最小元素位置了。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。
时间: 2024-05-15 16:19:47 浏览: 10
以下是改写后的二分搜索算法:
```
int binarySearch(int a[], int n, int x) {
int left = 0;
int right = n - 1;
int i = -1, j = -1; // 初始化 i 和 j 为 -1
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == x) {
i = j = mid; // 找到了 x,更新 i 和 j 的值
break;
} else if (a[mid] < x) {
i = mid; // 更新 i 的值为小于 x 的最大元素位置
left = mid + 1;
} else {
j = mid; // 更新 j 的值为大于 x 的最小元素位置
right = mid - 1;
}
}
if (i == -1 || j == -1) {
// 没有找到 x,返回小于 x 的最大元素位置和大于 x 的最小元素位置
return (a[i] < x ? i : j);
} else {
// 找到了 x,返回 x 在数组中的位置
return i;
}
}
```
在算法中,我们维护了两个变量 i 和 j,分别表示小于 x 的最大元素位置和大于 x 的最小元素位置。当找到 x 时,i 和 j 的值都被更新为 x 在数组中的位置。如果没有找到 x,我们返回小于 x 的最大元素位置和大于 x 的最小元素位置中的一个。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)