程序员成长之旅——二分查找时间与空间复杂度
程序员文章站
2024-03-20 09:54:34
...
时间复杂度
非递归
int binary_search(int* list, int len, int target)
{
int left = 0;
int right = len - 1;
int middle;
while (left < right)
{
middle = (left + right) / 2;
if (list[middle] = target)
{
printf("已找到该值,数组下标为:%d\n", middle);
return list[middle];
}
else if (list[middle] > target)
{
right = middle;
}
else if (list[middle] < target)
{
left = middle + 1;
}
}
printf("未找到该值!");
return -1;
}
递归
while (left <= right)
{
if (left > right)//查找不到
return -1;
int mid = left + (right-left) / 2;
if (target == list[mid])//查找到
return mid;
else if (target < list[mid])
return binary_search(list, left, mid, target);
else
return binary_search(list, mid + 1, right, target);
}
第一次有 n 个元素,第二次n/2个元素,以此类推第k次则为n/2^k个元素。
而时间复杂度一般都是取最坏结果的,并且是以k来作为衡量时间复杂度,
最坏结果,最后一次再剩一个元素,即n/2^k=1,得k=log2n,所以时间复杂
度为 O(logn)。
空间复杂度
递归
递归的深度*每次递归所需的辅助空间的个数
所以空间复杂度是:O(N) ( 递归一次要开辟一个空间)
非递归
由于辅助空间是常数级别的
所以:空间复杂度是O(1);
上一篇: 网页编写技巧:表单textarea有关焦点的用法大全!
下一篇: Md5,base64加密