c语言_Day12_07_11
c语言_Day12_07_111、二分查找算法
也称折半查找，最坏情况查找log2n次
算法如下：
[*]找到中间元素索引[左右下标平均值]
[*]通过中间下标找到中间元素
[*]判断：若中间元素小于目标值则修改左下标(left = mid + 1)；若中间元素大于目标值则修改右下标(right = mid - 1)；若相等则直接返回
[*]循环：当左下标不大于右下标时继续查找，反之则未找到元素，应跳出循环
int main()
{
// 查找数组
int arr[] = { 1,2,3,4,5,6,8,9 };
// 目标元素
int k = 3;
// 数组长度
int length = sizeof(arr) / sizeof(arr);
// 定义左右下标
int left = 0;
int right = length - 1;
// 定义中间下标
int mid;
// 当左下标仍不大于右下标时，查找仍在继续
while (left <= right)
{
// 计算中间下标
mid = (left + right) / 2;
// 若中间下标元素小于目标值，则修改左下标
if (arr < k)
{
left = mid + 1;
}
// 若中间下标元素大于目标值，则修改右下标
else if (arr > k)
{
right = mid - 1;
}
// 若中间下标元素等于目标值，则直接返回
else
{
printf("已找到k，数组下标为%d\n", mid);
break;
}
}
// 当左下标仍大于右下标时，未找到元素
if (left > right)
{
printf("未找到k\n");
}
return 0;
}
2、素数算法优化
基本算法：试除法
if (num > 1)
{
for (int i = 2; i < num; i++)
{
if (num % i == 0)
{
return 0;
}
}
return 1;
}
else
{
return 0;
}
优化：上述算法需要从2遍历至num-1，实际上对于一个整数i，若i = a * b，则a和b中至少有1个数字小于等于i开平方
int isPrime(int num)
{
if (num > 1)
{
// 1. 试除法
//for (int i = 2; i < num; i++)
//{
// if (num % i == 0)
// {
// return 0;
// }
//}
//2. 优化
for (int i = 2; i <= sqrt(num); i++)
{
if (num % i == 0)
{
return 0;
}
}
return 1;
}
else
{
return 0;
}
}
int main()
{
int count = 0;
for (int i = 201; i <= 300; i+=2) // 偶数不可能为素数
{
if (isPrime(i))
{
printf("%d\n", i);
count++;
}
}
printf("count = %d\n", count);
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15285915/3036584
页:
[1]