c++二分法查找有序序列中第一个小于等于于目标值的位置
时间: 2024-10-04 12:04:39 浏览: 5
二分查找(Binary Search),也叫折半查找,是一种在有序数组中搜索特定元素的高效算法。在C++中,它的基本思想是从数组中间开始,如果目标值小于中间元素,则在左半部分继续查找;如果目标值大于中间元素,则在右半部分查找,直到找到目标值或搜索范围为空。
下面是二分查找在一个有序整数数组`arr`中找到第一个小于等于`target`的元素的C++伪代码:
```cpp
int binarySearchFirstSmallerThan(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 如果mid大于目标值,说明第一个小于等于target的元素在mid的左边
if (arr[mid] > target)
right = mid - 1;
// 否则,如果mid不大于或等于target,那么我们继续在mid右边找
else
left = mid + 1;
}
// 返回第一个小于等于target的元素索引(注意不是target)
return left;
}
```
相关问题
c++ 二分法查找有序序列中最后一个小于等于于目标值的位置 代码
在 C++ 中,二分查找(Binary Search)通常用于已排序的数组中找到某个元素的确切位置。如果需要找到的是小于等于目标值的最大索引,可以在标准二分查找的基础上稍作修改。以下是简单的代码示例:
```cpp
#include <iostream>
// 二分查找函数,返回小于等于 target 的最大索引
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
// 如果目标值大于中间元素,则在右半部分继续查找
if (arr[mid] < target)
left = mid + 1;
// 否则,如果目标值小于等于中间元素,则更新左边界并检查下一个中间元素
else
right = mid - 1;
}
// 如果整个数组遍历完都没有找到满足条件的元素,返回数组长度作为插入位置
return left;
}
int main() {
int arr[] = {1, 3, 5, 6, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 7; // 搜索的值
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1)
std::cout << "Last index <= " << target << ": " << result << std::endl;
else
std::cout << "No element found smaller than or equal to " << target << std::endl;
return 0;
}
```
在这个例子中,`binarySearch` 函数会在 `arr[left...right]` 区间内寻找,当找到第一个大于 `target` 的元素时停止,并返回它的前一个位置作为结果。
C语言二分法查找有序数组,目标值的位置区间
二分法查找(Binary Search),也称为折半查找,是一种在有序数组中寻找特定元素的搜索算法。它的基本思想是从数组的中间元素开始,如果中间元素正好是要找的目标值,则搜索结束;如果目标值小于中间元素,就在数组左半部分继续查找;如果目标值大于中间元素,则在右半部分查找。这个过程会不断将搜索范围缩小一半,直到找到目标值或者搜索范围为空。
下面是C语言中的二分法查找算法的基本步骤:
```c
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int target) {
if (right >= left) {
int mid = left + (right - left) / 2; // 计算中间索引
// 如果中间元素就是目标值,返回其索引
if (arr[mid] == target)
return mid;
// 如果目标值小于中间元素,向左半部分查找
else if (arr[mid] > target)
return binarySearch(arr, left, mid - 1, target);
// 否则,在右半部分查找
else
return binarySearch(arr, mid + 1, right, target);
}
// 如果搜索范围为空,表示目标值不存在于数组中
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr);
int target = 5;
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1)
printf("元素在数组中的位置: %d\n", result);
else
printf("元素不在数组中.\n");
return 0;
}
```
当你调用`binarySearch`函数并传入数组、初始和结束索引以及目标值,它将返回目标值在数组中的位置,如果没有找到则返回-1。执行该代码后,你会得到目标值5在数组中的位置3。如果目标值不存在于数组中,函数会告知你“元素不在数组中”。