记得写递归终止条件,总是不记得
不同二分的返回值不同,注意区分
当二分边界移动的是l的时候注意死循环的发生

快速排序

个人错误总结

1.不可以用>=和<=
可能会造成越界问题

2.分界值的选择与递归传入条件
i会指向x所在位置的后一个数(i所指向的数大于等于x)
j会指向x所在位置的前一个数(j所指向的数小于等于x)
为了让所分区间仍然满足左边的小于等于x右边的大于等于x
对于不同的分界元素(用i或者用j)写法就不一样

3.swap的交换条件不可省
否则最后一次出循环的时候可能发生不必要的交换

代码模板

void quick_sort(int* q,int l,int r)
{
    if(l>=r)    return;
    int x=q[(l+r)>>1],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quick_sort(l,j);
    quick_sort(j+1,r);
}

另外一种

void quick_sort(int[] q,int l,int r)
{
    if(l>=r)    return;
    int x=q[(l+r+1)>>1],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j])
    }
    quick_sort(q,l,i-1);
    quick_sort(q,i,r);
}

归并排序

(详见之前的排序分享)
排序

二分算法

二分的本质是一部分元素满足题目性质,另一半部分不满足

整数二分

789. 数的范围
check函数的定义,我们一般是先考虑题目的条件,分成满足和不满足题意,把满足题意且包含mid的放于check()中写
并且要保证此时check(mid)是true
就像数的范围这道题,一半是小于该数,另一半是大于等于该数,就会考虑把大于等于mid放进if判断语句中,而不是小于该数
(即保证mid是被包含在该合法区域内)
一般是小于等于该数,另一半是大于该数,
就是if(check(mid)) 要让mid不能被直接排除在答案之外

int main()
{
    int l=0,r=n-1;
    while(l<r)
    {
        int mid=(l+r>>1)
        if(check(mid))  r=mid;
        else    l=mid+1;
    }
}

int main()
{
    int l=0,r=n-1;
    while(l<r)
    {
        int mid=(l+r+1>>1)
        if(check(mid))  l=mid;
        else    r=mid-1;
    }
}

浮点数二分

790. 数的三次方根
由于浮点数是没有向上向下取整的,所以就可以直接进行除也不用+1,或者-1
不过要小心负数的存在,还有r-l的值会影响结果精度

#include<iostream>
using namespace std;
int main()
{
    double x;
    cin>>x;
    double r,l;
    if(x>=0)
        r=x,l=0;
    else
        r=0,l=x;
    while(r-l>1e-8)
    {
        double mid=(r+l)/2;
        if(mid*mid*mid>=x)  r=mid;
        else l=mid;
    }
    printf("%.6f",r);
}