使用折半查找法实现给定一个有序(非降序)数组a,可含有重复元素,求最大的i使得a[i]小于target,不存在则返回 -1
时间: 2023-06-05 15:47:52 浏览: 269
折半查找法,也称二分查找法,是一种常用的查找算法。它的基本思想是:将有序数组分成两部分,取中间位置的元素与目标值进行比较,如果相等则返回该位置,如果中间位置的元素大于目标值,则在左半部分继续查找,否则在右半部分继续查找,直到找到目标值或者查找范围为空。
对于本题,我们可以使用折半查找法来实现。具体步骤如下:
1. 初始化左右指针left和right,分别指向数组的起始位置和结束位置。
2. 在循环中,计算中间位置mid,取出中间位置的元素与目标值进行比较。
3. 如果中间位置的元素小于目标值,则将左指针left移动到mid+1的位置。
4. 如果中间位置的元素大于等于目标值,则将右指针right移动到mid-1的位置。
5. 如果左指针left大于右指针right,则说明不存在小于目标值的元素,返回-1。
6. 如果存在小于目标值的元素,则继续循环,直到找到最大的i使得a[i]小于target。
下面是具体的代码实现:
```
int binary_search(int a[], int n, int target) {
int left = , right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
```
在上面的代码中,我们使用了左闭右闭的区间表示法,即[left, right]表示查找范围。在循环中,我们计算中间位置mid,如果中间位置的元素小于目标值,则将左指针left移动到mid+1的位置,否则将右指针right移动到mid-1的位置。最后返回right即可。
需要注意的是,如果数组中不存在小于目标值的元素,则right的值为-1。
相关推荐
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)