C语言之二分查找
程序员文章站
2024-03-17 15:34:10
...
一、二分查找
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。该算法一开始令 [low, high] 为整个序列的下标区间,然后每次测试当前 [low, high] 的中间位置 mid = (left + right) / 2,判断 array[mid] 与欲查询的元素 num 的大小:
- 若 array[mid] == num,说明查找成功,退出查询;
- 若 array[mid] > num,说明元素 num 在 mid位置的左边,因此往左子区间 [left, mid - 1] 继续查找;
- 若 array[mid] < num,说明元素 num 在 mid位置的右边,因此往左子区间 [mid + 1, right] 继续查找;
int binarySearch_0(int *array, int low, int high, int num)
{
while(low <= high)
{
int mid = (low + high)/2; //折半
//mid = low + (high - low) / 2可以避免low + high溢出
if(array[mid] > num) //若查找值比中值小
high = mid -1; //最高下标调整到中位下标小一位
else if(array[mid] < num) //若查找值比中值大
low = mid + 1; //最低下标调整到中位下标大一位
else
return mid + 1; //若相等则说明mid+1即为查找到的位置
}
return 0; //返回-1,即没有找到
}
进一步地,如果要求出序列中第一个大于等于 num 的元素位置以及第一个大于 num 的元素的位置,这样元素 num 在序列中的存在区间就是左闭右开区间 [low, high)。
//第一个大于等于 num 元素的位置
int binarySearch_1(int *array, int low, int high, int num)
{
while(low < high)
{
int mid = (low + high)/2;
if(array[mid] >= num)
high = mid;
else
low = mid + 1;
}
return low + 1;
}
//第一个大于 num 元素的位置
int binarySearch_2(int *array, int low, int high, int num)
{
while(low < high)
{
int mid = (low + high)/2;
if(array[mid] > num)
high = mid;
else
low = mid + 1;
}
return low + 1;
}
总结起来,整体代码如下
#include<stdio.h>
//元素 num 所在位置
int binarySearch_0(int *array, int low, int high, int num)
{
while(low <= high)
{
int mid = (low + high)/2; //折半
//mid = low + (high - low) / 2可以避免low + high溢出
if(array[mid] > num) //若查找值比中值小
high = mid -1; //最高下标调整到中位下标小一位
else if(array[mid] < num) //若查找值比中值大
low = mid + 1; //最低下标调整到中位下标大一位
else
return mid + 1; //若相等则说明mid+1即为查找到的位置
}
return 0; //返回-1,即没有找到
}
//第一个大于等于 num 元素的位置
int binarySearch_1(int *array, int low, int high, int num)
{
while(low < high)
{
int mid = (low + high)/2;
if(array[mid] >= num)
high = mid;
else
low = mid + 1;
}
return low + 1;
}
//第一个大于 num 元素的位置
int binarySearch_2(int *array, int low, int high, int num)
{
while(low < high)
{
int mid = (low + high)/2;
if(array[mid] > num)
high = mid;
else
low = mid + 1;
}
return low + 1;
}
int main()
{
int num;
int array[] = {3, 7, 7, 7, 8, 11, 21, 21, 33, 52};
while(scanf("%d", &num) != EOF)
{
int pos = binarySearch_0(array, 0, sizeof(array)/sizeof(array[0]), num);
if(pos)
printf("%d的位置是%d\n", num, pos);
else
printf("未找到%d\n", num);
}
return 0;
}
二、快速幂
快速幂基于二分法思想:
- 若 b 为奇数,那么有a^b = a * a ^ (b-1);
- 若 b 为偶数,那么有a^b = a ^(b/2)* a ^ (b/2);
typedef long long LL;
//求a^b % m 递归
LL binaryPow_0(LL a, LL b, LL m)
{
if(b == 0)
return 1;
if(b & 1)
return a * binaryPow_0(a, b-1, m) % m;
else
{
LL mul = binaryPow_0(a, b/2, m);
return mul * mul % m;
}
}
/*
求a^b % m 递归
13的二进制为 1101,13 = 2^3 + 2^2 + 2^0 = 8 + 4 + 1;
a^13 = a^(8+4+1)即把任意的 a^b 表示为a^(2k)若干项的乘积
*/
LL binaryPow_1(LL a, LL b, LL m)
{
LL mul = 1;
while(b > 0)
{
if(b & 1)
{
mul = mul * a % m;
}
a = a * a % m; //让 a 平方a->a^2->a^4->a^8
b >>= 1;
}
return mul;
}