在数组中找到最接近0的负数（logn复杂度）
我有一个问题：编写一个函数来获取整数及其大小的升序数组。给出数组至少包含一个负数和一个正数，我需要找到最接近该数的负数0.
例如： [-30,-25,-18,-10,11,11,20,30]
该函数将返回 -10.
问题是我需要O(log n)复杂地做这件事，我不知道如何做到这一点。我只用O(n).
`
int f(int* arr, int size)
{
int i;
int result = arr[0];
for (i = 1;i < size;i++)
{
if (arr[i] < 0 && result < arr[i])
result = arr[i];
else
return result;
}
return result;
}
回答
这是一个简单的二进制搜索的 C 实现，它在 O(log n) 时间内工作。
#include <stdio.h>
int find(int *arr, size_t size)
{
size_t bot = 0;
size_t top = size; // it will never be top
size_t dif;
while((dif = top - bot) > 1) {
size_t mid = bot + dif / 2;
if(arr[mid] >= 0) { // eliminate non-negatives
top = mid;
}
else {
bot = mid;
}
}
return arr[bot];
}
int main(void) {
int arr[] = { -30, -25, -18, -10, 11, 11, 20, 30 };
size_t size = sizeof arr / sizeof arr[0]; //parentheses only needed for types
printf("%dn", find(arr, size));
}
我喜欢使用二分搜索，这样top元素就永远不是候选元素。
程序输出：
-10