C语言编程题（七）二分算法

算法"/>

C语言编程题（七）二分算法

二分查找

一个有序顺序表一般来说最有效的查找方式就是二分查找，核心思想就是通过不断的折半区间来最终确定待查值的位置。
而查找的时候会出现两种情况，第一种情况是待查值确切在有序顺序表中，那么返回值就是该元素在数组中的下标。
而第二种情况是确定一个范围，比如查找比某值大的第一个位置，亦或是查找比某值小的一个第一个位置。
上述两种情况的算法实现有些许的差别

查找某值的在有序顺序表中的下标

int solve(const int A[],int start,int end,int target)
{int left = start,right = end,mid;while(left <= right){mid = (left + right) / 2;if(A[mid] == target)return mid;if(A[mid] > target)right = mid - 1;elseleft = mid + 1;}return - 1;
}

• start，end分别是待查表中开始下标和结束下标
• 当left > right 此时依然没有找到待查值，说明不在数组中，返回-1

查找某个单区间范围（第一个比待查值大的下标或者第一个比待查值小的下标）

给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

例如，对于 2 5 9 1 3 4 6 7 8 20这个数列，当p = 8时
取2，3，4，5，6，7，8，9这八个数可以组成完美数列
或者取3，4，5，6，7，8，9，20也可以。

很自然的应该把输入数组进行从大到小排序，把每个元素依次当作最小值，其后的子列中不会有比他小的，往后查找到第一个比该元素大的元素对应的下标。

#include <stdio.h>
void QuickSort(long long *,int,int);
int getBig(int a,int b)
{if(a >= b)return a;return b;
}
int solve(const long long A[],int start,int end,long long target)
{int mid,left,right;left = start+1,right = end - 1;while(left < right){mid = (left + right) / 2;if(A[mid] <= target)left = mid + 1;else right = mid;}return left;
}
int main()
{int N,i,count;long long P,max;long long A[100000];while(scanf("%d%lld",&N,&P) == 2){for(i = 0;i < N;i++)scanf("%lld",&A[i]);QuickSort(A,0,N - 1);count = 0;for( i = 0;i < N;i++){max = A[i] * P;if(max >= A[N - 1])count = getBig(count,N - i);else{count = getBig(count,solve(A,i,N,max) - i);}}printf("%d\n",count);}return 0;
}int partition(long long A[],int left,int right)
{long long pivot = A[left];while(left < right){while(left < right && A[right] >= pivot)right--;if(left < right)A[left] = A[right];while(left < right && A[left] <= pivot)left++;if(left < right)A[right] = A[left];}A[left] = pivot;return left;
}
void QuickSort(long long A[],int left,int right)
{if(left < right){int pivotPos = partition(A,left,right);QuickSort(A,left,pivotPos - 1);QuickSort(A,pivotPos + 1,right);}
}

• quicksort 是快排算法用于让输入的无序列表先有序。
• A[mid] <= target,说明比target大的元素至少在mid + 1的位置
• A[mid] > target 说明比target大的元素最小的位置小于等于mid的位置。

二分法的拓展问题

二分法的思想远远不止应用于有序顺序表的查找，它还有一个很重要的用途是用于单调函数的求根（可以是抽象函数的求解，也可以是现实具体问题的求解），下面用几个编程题来说明问题。

求解函数f(x) = x² - 2的根，精确到小数点后五位
具有初中知识就知道该方程的根是 根号2，但是对于计算机来说并不知道根号的含义，我们必须求解具体的浮点值。
首先由单调性和零点定理，可以确定方程的根在（1，2）内，将其分别作为上界和下界。判断mid（这里是1.5）代入原方程和零的大小，如果比零大，说明根在mid的右边，如果比0小说明根在mid的左边。根据判断结果就能更新上下界（实际上二分法可以看作是零点定理的实现），当上下界的差值小于给定精度后就可以跳出循环了，此时的mid值就是我们要求的近似根。

#include <stdio.h>
#define EPS 10E-5
double f(double x)
{return x * x - 2;
}
double solve(double left,double right)
{double mid = left;while(right - left  > EPS){mid = (left + right) / 2;if(f(mid) == 0)break;if(f(mid) > 0)right = mid;elseleft = mid;}return mid;
}
int main()
{printf("%.5lf",solve(1,2));return 0;
}

二分算法不仅可以用于解决这类的抽象问题，还可以解决具体问题


题目的大意就是给出两个正整数，其中一个正整数的进制已给，现在求另一个正整数的进制，使得二者相等。如果没有答案则输出Impossible

如果A和B相等，则二者的进制肯定是相等的，如果B比A大的话，那么B的进制数肯定比A小，且数字随进制的增大而减小，这就相当于一个单调递减的函数。
分析至此，就可以判断用二分法可以解此题。

• 因为输入的数字可能会包含字母，所以必须得用字符串来接收
• 将得到的两个字符串都转换成最大的三十六进制来比大小
• 大的数字进制数较小,小的必然较大
• 因为所给进制的数字可能是第一个也可能是第二个，所以当是第二个的时候可以交换一下
• 本题核心在于求进制的上下限，对于下限，可以通过字符串已经出现的最大数字加1的方式得到，比如99这个数字，当前已经出现的最大数字是9，那么进制数至少是10
• 对于上限，如果已知进制的数较小，那么待求数的进制数必然比已知进制数要小啊，例如已知6所给为10进制，待求110的进制数，那么110的进制必然是要小于10的；如果已知进制的数较大，那么待求数的进制数比如要大一点，例如 已给数字是1000，已知其进制数为10.如果待求数字是一位，比如6，那么无论其取多少进制都不可能相等。二者可能相等的情况至少数字为二位数10，此时的进制数是1000，如果比10要大，那么所要求的进制数就比1000要小。由此可知待求数字的进制数的上限是第一个数字。

#include <stdio.h>
#include <string.h>
unsigned long long max(unsigned long long a, unsigned long long b)
{if(a >= b)return a;return b;
}
int map(char ch)
{if(ch >= 'a')return ch - 87;return ch - '0';
}
unsigned long long str_to_num(const char *str, unsigned long long radix)
{int i = 0;unsigned long long sum = 0;while(str[i] != '\0'){sum *= radix;sum += map(str[i]);i++;}return sum;
}
int findLargestDigit(const char *str)
{int ans = 1,i = 0;while(str[i] != '\0'){if(map(str[i]) > ans)ans = map(str[i]);i++;}return ans + 1;
}
unsigned long long solve(char * str,unsigned long long num,unsigned long long left, unsigned long long right)
{unsigned long long mid,res;while(left <= right){mid = (left + right) / 2;res = str_to_num(str,mid);if(res == num)return mid;if(res > num)right = mid - 1;elseleft = mid + 1;}return -1;
}
int main()
{char str1[11],str2[11],temp[11];unsigned long long low,high,radix,num1,num2,cmp,result;int tag;while(scanf("%s%s%d%llu",str1,str2,&tag,&radix) == 4){if(tag == 2){strcpy(temp,str1);strcpy(str1,str2);strcpy(str2,temp);}num1 = str_to_num(str1,36);num2 = str_to_num(str2,36);cmp = str_to_num(str1,radix);low = findLargestDigit(str2);if(num1 == num2)result = radix;else if(num1 > num2){result = solve(str2,cmp,radix + 1,cmp);}else{result = solve(str2,cmp,low,radix - 1);}if(result == -1)puts("Impossible");elseprintf("%llu\n",result);}return 0;
}