
🌈这里是say-fall分享,感兴趣欢迎三连与评论区留言 🔥专栏: 《C语言从零开始到精通》 《C语言编程实战》 《数据结构与算法》 《小游戏与项目》 💪格言:做好你自己,你才能吸引更多人,并与他们共赢,这才是你最好的成长方式。
我们在计算时间复杂度的时候总是喜欢看循环的次数,实际上单看循环次数是很容易出错的,下面我们来看一下
void f(int n)
{
int x = 0;
for (int i = 1;i < n;i *= 2)
{
x++;
}
printf("%d\n", x);
}
int main()
{
f(8);
f(512);
f(1024);
return 0;
}单看循环的话应该是一个O(n)的时间复杂度,因为循环了i最后的定值是n 但是需要注意的是:这里面并不是
i++,而是i *= 2; 实际上每次是乘2,这就导致了执行的操作数其实是122…=n=2^x; 这样的话x = log n,也就是O(log n)的时间复杂度;
int BinarySearch(int* nums,int numsSize,int x)
{
//左闭右闭类型
int left = 0;
int right = numsSize - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == x)
return mid;
else if (nums[mid] > x)
right = mid - 1;
else
left = mid + 1;
}
return -1;
}int BinarySearch(int* nums, int numsSize, int x)
{
//左闭右开类型
int left = 0;
int right = numsSize;
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == x)
return mid;
else if (nums[mid] > x)
right = mid;
else
left = mid + 1;
}
return -1;
}有两种写法的原因是:二分查找的本质是区间查找
特性 | 左闭右闭 [left, right] | 左闭右开 [left, right) |
|---|---|---|
右边界初始化 | right = size - 1 | right = size |
循环条件 | left <= right | left < right |
右边界更新 | right = mid - 1 | right = mid |
左边界更新 | left = mid + 1 | left = mid + 1 |
区间含义 | 包含左右边界 | 包含左边界,不包含右边界 |
空区间条件 | left > right | left == right |
搜索范围 | [left, right] | [left, right) |
元素数量 | right - left + 1 | right - left |
边界检查 | 需要检查 mid 是否在 [0, size-1] 内 | 需要检查 mid 是否在 [0, size) 内 |
对比维度 | 二分查找 | 遍历查找(线性查找) |
|---|---|---|
时间复杂度 | O(log n) | O(n) |
空间复杂度 | O(1) | O(1) |
前提条件 | 必须是有序数组 | 对数据顺序无要求 |
查找效率 | 非常高效,数据量大时优势明显 | 效率较低,随数据量线性增长 |
这里举个例子说明一下,数据量大的时候二分查找究竟有多效率
数据规模 | 二分查找最大比较次数 | 遍历查找平均比较次数 |
|---|---|---|
10个元素 | 4次 | 5次 |
100个元素 | 7次 | 50次 |
1000个元素 | 10次 | 500次 |
100万元素 | 20次 | 50万次 |
再来看看二分查找的不足之处
不足方面 | 具体表现 | 影响程度 |
|---|---|---|
数据必须有序 | 需要预先排序,排序成本O(n log n) | 高 |
内存访问不连续 | 跳跃式访问,缓存不友好 | 中 |
不适合小数据 | 数据量小时,优势不明显甚至更慢 | 低 |
最重要的就是,二分查找是一个数组结构的算法,这就导致了一旦有增删查改就很不方便