二分

并不是数组有序才可以用二分算法，只要有二段性就可以使用 中间下标的几种求法：

1.int mid=(left+right)/2 可能会超出数据范围 2.int mid=(left+right)>>1 3.int mid=left+(right-left)/2 不会超出数据范围 当数据个数为偶数时： int mid=left+(right-left)/2，求的是中间偏左边的下标 int mid=left+(right-left+1)/2，求的是中间偏右边的下标

朴素的二分

while(left<=right)
{
    int mid=left+(right-left)/2;
    if(...)
        left=mid+1;
    else if(...)
        right=mid-1;
    else
        return ...;
 }

查找区间左端点

while(left<right)
{
    int mid=left+(right-left)/2;
    if(...)
        left=mid+1;
    else
        right=mid;
 }

查找区间右端点

while(left<right)
{
    int mid=left+(right-left+1)/2;
    if(....)
        left=mid;
    else
        right=mid-1;
 }

前缀和

给你一个数组 nums 创建一个数组dp，表示 nums ，的前1数的和，前2个数的和 …… 一般要自己寻找递推公式，例 dp[i]=dp[i-1]+nums[i] 要注意前缀和数组的下标是从1还是从0开始。 具体问题，具体分析

---

位运算

常见的位运算 &（按位与）：有0就是0 |（按位或）：有1就是1 ^（异或）：相同的为0，不相同的为1，无进位加法 a^a=0; a^0=a;

快排

三路划分+随机选取key

int Getrand(vector<int>& nums, int left, int right)
{
    return nums[rand() % (right - left + 1) + left];
}

void qsort(vector<int>& nums, int l, int r)
{
    if (l >= r)
        return;
    int key = Getrand(nums, l, r);
    int left = l - 1, right = r + 1, i = l;
    while (i<right)
    {
        if (nums[i] < key)
            swap(nums[++left], nums[i++]);
        else if (nums[i] == key)
            i++;
        else
            swap(nums[--right], nums[i]);
    }

    qsort(nums, l, left);
    qsort(nums, right, r);
}

归并

int tmp[50000];

void mergesort(vector<int>& nums, int left, int right)
{
    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    //分割数组
    mergesort(nums, left, mid);
    mergesort(nums, mid + 1, right);
    //开始合并数组
    int cur1 = left, cur2 = mid + 1, i = 0;
    while (cur1 <= mid && cur2 <= right)  //排升序
    {
        if (nums[cur1] < nums[cur2])
            tmp[i++] = nums[cur1++];
        else
            tmp[i++] = nums[cur2++];
    }

    while (cur1 <= mid)
        tmp[i++] = nums[cur1++];
    while (cur2 <= right)
        tmp[i++] = nums[cur2++];

    for (int i = left; i <= right; i++)
        nums[i] = tmp[i - left];
}