前言
事实上，我们在解决实际问题时一般会用二分答案而不是二分查找。今天我就来给大家介绍一下二分查找这种由二分法衍生出来的办法。

程序设计思路
相比于二分查找，二分答案有极为重要的一点不同——check思想。也就是说，每查到一个答案都将其经过特定的程序后再与基准数比较。这样看来，二分答案其实就是在二分查找的基础上加了一步检查。
二分查找往往是在一堆数里查找答案，而二分答案则通常面对一个范围，这也是它们之间的一显著区别。

代码实现
解方程中经常会用到二分答案，因为它的范围很广，而且往往包含浮点数答案。来看下面这题：

    这题目明摆着要我们用二分答案，否则如果用浮点数试过去效率太低，容易TLE。看代码：

#include <bits/stdc++.h>
double a,b,c,d,l,m,r;//a、b、c、d如题意，l、m、r分别为左、中、右指针
double f(double x){//检查解是否合法，算一遍方程
    return a*pow(x,3)+b*pow(x,2)+c*x+d
}
int main(){
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
    for(int i=-100;i<100;i++){//由题意得有200个整数区间，分别查找
        l=i;
        r=i+1;
        if(f(l)==0){//特判，正好相等时直接输出
            printf("%.2lf ",l);
            continue;
        }
        if(f(l)*f(r)>=0) continue;//用题目中所给式子判断
        while(r-l>0.001){//不断缩小范围
            m=(l+r)/2;
            if(f(l)*f(m)<=0) r=m;
            else l=m+0.001;
        }
        printf("%.2lf ",m);
    }
    return 0;
}

代码中的f()函数就是所谓check思想。这样一来便很好理解了。

结语
二分答案作为二分算法的一个衍生分支，能够解决很多问题。我是faryou，再见！

前言
在信奥中，二分算法是一种非常重要的方法。利用它，我们在某些场合中寻找数时就不必要遍历数组，大大提高了效率。今天我们来学习二分算法的基本方法。

程序设计思路
有这样一个问题：给你一个数组，数组里面的数已经按数值大小倒序排列，请从中找到某个数，要求不得遍历数组。
这里需要注意，数组里的数已经降序排列，这一点对我们要进行的查找是有帮助的。我们可以利用数之间的大小关系，进行查找。比如说，可以先找到数组中间的那个数，与基准数（要找的数）进行比较。如果基准数大于这个数，那么我们就可以确定基准数在这个数的左侧，反之则在这个数的右侧。这样一直循环，直到找到基准数。
这就是二分查找的精髓。

代码实现
直接看题：

这是二分算法的模板题，思路已经有了，直接上代码——

#include <bits/stdc++.h>
int a[1000005],n,m,aq;//a存输入的数据，n、m同题意，aq临时存要查找的数
int search(int iq){
    int left=1,right=n,mid=(1+n)/2;//确定左指针、右指针、中央
    while(left<right){//当左右指针相遇时，循环结束
        mid=(left+right)/2;
        if(a[mid]>=iq) right=mid;
        else left=mid+1;
    }//不断更新左、右、中指针
    if(a[left]==iq) return left;
    else return -1;
}

int main(){//main里全是输入和输出，不讲了
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%d",&aq);
        printf("%d ",search(aq));
    }
    return 0;
}

可以看到，这里使用了左右两个指针解决问题。程序并不难写，关键在思路。

总结
二分算法是一种能够大大提升查找效率的方法。之后我还会为大家带来由二分算法衍生出的二分答案和三分算法。我是faryou，再见！

前言
有时候，我们需要对数组进行排序，而在算法中，由于对效率的追求，选择排序和冒泡排序已经无法满足我们的需求。这时，我们就需要使用效率更高的快排。

程序设计思路
在快速排序中，我们需要两个指针，分别是左指针和右指针,即left和right。他们从数组两端出发，相向而行。之后找到中点，作为基准数，比基准数大的和小的各自到一边（为讲解方便，这里讲升序）。当左右指针相遇时，我们已经将所有的数分为两组。之后，我们再次进行相同操作，直到将所有的数分组不断细化，最后每个数一组。
这样一来，我们不难想到递归。即当主程序结束后，我们对两组数再次调用主程序本身，之后再次调用。
这种方法的时间复杂度是O(n log n)。

代码实现

void qsort(long long a[],long long left,long long right){三个参数分别为数组名、左右端点
    long long i,j,t;//i、j分别存放左右端点
    if(left>=right) return;//特判，用于最后退出程序
    int x=(left+right)/2;//取中点
    swap(a[x],a[left]);//防止重复
    t=a[left];//基准数
    i=left;
    j=right;
    while(i<j){
        while(a[j]>=t && i<j) j--;//j不断向左，直到发现小数
        while(a[i]<=t && i<j) i++;//i不断向右，直到发现大数
        if(i<j) swap(a[i],a[j]);//如果i比j小，交换
        else break;
    }
    swap(a[left],a[i]);//调换回来
    
    //再次调用
    if(left<i) qsort(a,left,i-1);
    if(right>i) qsort(a,j+1,right);
}

sort( , , )函数使用
在C++的STL库中，有一个sort函数，可以省去我们自写快排的烦恼。
sort( , , )函数的第一个参数是数组头地址，第二个参数是数组尾地址。第三个是cmp函数名称。下面是对数组x[ ]进行排序的代码：

int k=sizeof(x)/sizeof(x[0];//获取数组长度
sort(x,x+k,);//在默认升序序情况下，无需编写cmp()函数

当我们需要对数组进行降序排序时，就需要自写cmp函数，像这样：

bool cmp(int a,int b){//int为数组数据类型
    return a>b;
}

int k=sizeof(x)/sizeof(x[0];//获取数组长度
sort(x,x+k,cmp);

sort还可以进行结构体排序，像下面这样：

bool cmp(class a,class b){
    return a.num<b.num;//降序，如需升序请将>改为<；此处对结构体中的元素num进行排序
}

sort函数的时间复杂度为O(n log n)。

结语
快排极大的提高了效率，使得程序运行速度更快，节省了时间。我是faryou，下次见！

前言
通常情况下，我们在使用程序进行幂运算时，会利用循环乘法或pow( , )解决。但对于数据非常大的情况，这样做非常影响效率，很容易导致超时。因此，快速幂应运而生。

程序设计思路
快速幂基于二进制进行。通常情况下，我们会将其封装为一个函数binpow( , )。下面举个例子说明其原理：
我们要计算3的13次方，常规做法是：用for循环使一个变量从1开始每次乘3，这里数据小，没有问题，但如果是3100000000呢（不考虑数据溢出）？这样算肯定不对。
快速幂就很好的解决了这个问题，我们可以将3的13次方分解为：
3的13次方 = 3的8次方 3的4次方 3
这样一来，我们只需要计算3的2n次方即可，即每次进行平方运算。节省了大量时间。

代码实现

int quick(int a,int b){//计算a^b
    int res = 1;//从1乘起
    while(b>0){
        if(b&1) res=res*a;//当a（二进制）的这一位是1时，乘a
        a=a*a;//计算a^2
        b>>=1;//答案的一位（二进制）解决
    }
    return res;
}

结语
快速幂在很大程度上提升了效率，使得程序速度更快。我是faryou，再见！

前言
在学习计算机的过程中，我们会碰到不同的进制，如二进制、十六进制等。而这些进制之间的转换，又成为了一个问题。现在，我们来学习写一个程序，实现二~十六进制之间的进制转换。

程序设计思路
一般情况下，要解决一个算法问题，首先要在数学上解决它。进制就代表着满几进一。因此，我们在进制转换时，只需要不断地除以进制数，并将余数连起来，就是新的数了。在进制转换时，通尝使用短除法。如将256转换为十六进制数：

16 l 2 5 6

16 l 1 6············0

16 l 1············0

0············1

故256=0x100。
在真正的写程序的时候，由于十六进制中的10~15用字母A~F表示，因此我们不能直接用int相加，而应该用字符串存数据。

代码实现
以下为题目要求及代码：
202407051720140869844401.png

#include <bits/stdc++.h>
using namespace std;
int n,m,ten;//n、m为题目中原义，ten为被转换的数的十进制
char a[15],ans[15];//a存输入，ans存输出
int n_ten(int n){//n进制→十进制
  int answer=0;//answer为结果
  for(int i=0;a[i]!='\0';i++){//数学方式：十进制数=n进制数的第i位数*n^(i-1)
    if(a[i]>='0' && a[i]<='9') answer=answer*n+a[i]-48;
    if(a[i]>='A' && a[i]<='F') answer=answer*n+a[i]-55;
  }
  return answer;
}
void ten_m(int a,int m){//十进制→m进制，即上面的短除法
  int b=0,i=a;//b为计次，i为十进制数
  while(i>0){//在i除完之前循环
    if(i%m<=9) ans[b]=i%m+48;
    if(i%m>=10) ans[b]=i%m+55;
    i = (i-i%m)/m;
    b++;
  }
  return ;
}
//以上两个函数都使用了ASCLL码相关知识，请自行查表
int main(){
  scanf("%d%s%d",&n,a,&m);
  ten=n_ten(n);
  if(m!=10){
    ten_m(ten,m);
    int n=strlen(ans);//获取长度
    for(int i=n-1;i>=0;i--) printf("%c",ans[i]);
  }
  else printf("%d",ten);
  return 0;
}

结语
进制转换最主要是在数学上理解这个方法，之后就是对照数学方式写程序了。我是faryou，再见！