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

桃扇骨 2022-10-29 10:24 97阅读 0赞

#### 二分查找 ####

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

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

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;
            else
                left = 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) = x2 \- 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;
            else
                left = mid;
        }
        return mid;
    }
    int main()
    { 
        printf("%.5lf",solve(1,2));
        return 0;
    }

二分算法不仅可以用于解决这类的抽象问题，还可以解决具体问题  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 1]  
**题目的大意就是给出两个正整数，其中一个正整数的进制已给，现在求另一个正整数的进制，使得二者相等。如果没有答案则输出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;
            else
                left = 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");
            else
                printf("%llu\n",result);
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70]: /images/20221024/e1b247dc00b44dfc8b864222cedaac95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 1]: /images/20221024/022c21b7260d444089f7210d041e8375.png