时间复杂度得是log2(n)
时间: 2024-01-12 16:04:49 浏览: 24
如果你要求时间复杂度为 O(log n),那么你可以使用二分查找算法来找到数组中比目标值小的最大数。以下是相应的示例代码:
```cpp
#include <iostream>
int binarySearch(int arr[], int left, int right, int target) {
int max_smaller = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
max_smaller = arr[mid];
left = mid + 1;
} else {
right = mid - 1;
}
}
return max_smaller;
}
int findMaxSmaller(int arr[], int size, int target) {
return binarySearch(arr, 0, size - 1, target);
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 4;
int result = findMaxSmaller(arr, size, target);
std::cout << "The maximum number smaller than " << target << " is: " << result << std::endl;
return 0;
}
```
在这个示例代码中,`binarySearch`函数使用二分查找算法来找到数组中比目标值小的最大数。时间复杂度为 O(log n)。输出结果将会是"The maximum number smaller than 4 is: 3"。你可以根据自己的需求修改代码来适应不同的情况。