首页 > 编程语言 >第一章 基础算法一

第一章 基础算法一

时间:2023-02-12 22:57:36浏览次数:52  
标签:二分 满足条件 while int 基础 mid 第一章 算法 区间

第一章 基础算法一

快速排序

quick_sort(int q[], int l, int r)

q是待排序数组,l是待排序区间的左边界,r是右边界

  1. 确定分界点x,可以取左边界的值q[l],或右边界的值q[r],或者中间位置的值q[(l + r)>>1]
  2. 根据基准值,调整区间,使得左半边区间的值全都≤ x,右半边区间的值全都≥ x
    采用双指针,左指针i从左边界l-1开始,往右扫描,右指针j从右边界r+1开始,往左扫描
    当满足条件q[i] < x时,i右移;直到不满足条件时,i停下;开始移动j
    当满足条件q[i] > x时,j左移;直到不满足条件时,j停下;交换q[i]q[j]
    将i右移一位,j左移一位,重复上面的操作,直到ij相遇。
    此时左半区间的数都满足≤x,且左半区间的最后一个数的下标为j,右半区间的数都满足≥ x,且右半区间的第一个数的下标为i
  3. 递归处理左右两段,递归操作[l, j][j + 1, r]区间,或者[l, i - 1][i,r]区间即可

代码模板

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 (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

注意要点

当区间划分结束后,左指针i和右指针j的相对位置,只有2种情况
i = j + 1 i = j(此时i和j指向的元素,恰好等于基准值x
若用j来作为区间的分界,则[l, j] 都是≤x[j + 1, r]都是≥x

若用i来作为区间的分界,则[l, i - 1]都是≤x[i, r]都是≥x

当取i作为分界的话,基准值x不能取到左边界q[l],否则会出现死循环,比如用例[1,2]。此时基准值可以取q[r],或者q[l + r + 1 >> 1],注意取中间位置的数时,要加个1,避免l + r >> 1的结果为l

当取j作为分界的话,基准值x不能取到右边界q[r],否则会出现死循环。此时基准值可以取q[l],或者q[l + r >> 1]

归并排序

  1. 确定分界点(一般是最中间) mid = (l + r) >> 1
  2. 对左右两个区间递归排序
  3. 将左右两个有序数组归并,合二为一(使用双指针)

时间复杂度O(nlogn)

代码模板

int binary_search_1(int l, int r) {
    while(l < r) {
        int mid = l + r + 1 >> 1;  
        // 当下面是 l = mid 这样来更新的话,这里计算mid时要多加1,否则会出现边界问题
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

二分查找

整数二分

二分的本质不是单调性,有单调性一定可以二分,可以二分不一定有单调性
二分的本质是边界,假设给定一个区间,如果能够根据某个条件,将区间划分为左右两部分,使得左半边满足这个条件,右半边不满足这个条件(或者反之)。就可以用二分来查找左右两部分的边界点。

Image

寻找红色二分点

  1. mid = l + r + 1 >> 1
  2. 判断mid 是否满足条件,check(mid)
  3. 如果mid 满足条件,那么答案(红色边界点)一定在[mid,r]之间,此时更新l = mid
  4. 如果mid 不满足条件,那么答案(红色边界点)一定在[l,mid-1]之间,此时更新r = mid - 1

注意,当采用l = midr = mid - 1这种更新方式时,计算mid时,要加上1(向上取整),即mid = l + r + 1 >> 1。否则,在l = r - 1时,计算mid时若不加1,则mid = l + r >> 1 = l,这样更新l = mid,就是l = l,会导致死循环。所以要向上取整,采用mid = l + r + 1 >> 1

模板

int binary_search_1(int l, int r) {
    while(l < r) {
        int mid = l + r + 1 >> 1;  
        // 当下面是 l = mid 这样来更新的话,这里计算mid时要多加1,否则会出现边界问题
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

寻找绿色二分点

  1. mid = l + r >> 1
  2. 判断mid 是否满足条件,check(mid)
  3. 如果mid 满足条件,那么答案(绿色边界点)一定在[l,mid]之间,此时更新r = mid
  4. 如果mid 不满足条件,那么答案(绿色边界点)一定在[mid + 1,r]之间,此时更新l = mid + 1

同理,当采用r = midl = mid + 1这种更新方式时,计算mid时不能加1,在l = r - 1时,若计算mid时加1,则mid = l + r + 1 >> 1 = r,这样更新r = mid。就是r = r,会导致死循环。

模板

int binary_search_2(int l, int r) {
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

浮点数二分

相比整数二分,浮点数二分无需考虑边界问题,比较简单。

当二分的区间足够小时,可以认为已经找到了答案,如当r - l < 1e-6 ,停止二分。

或者直接迭代一定的次数,比如循环100次后停止二分。

数的三次方根

给定一个浮点数 n,求它的三次方根。

输入格式

共一行,包含一个浮点数 n。

输出格式

共一行,包含一个浮点数,表示问题的解。

注意,结果保留 6 位小数。

数据范围

−10000≤n≤10000

输入样例:

1000.00

输出样例:

10.000000
#include <iostream>
using namespace std;

const double esp = 1e-8;

int main() {
    double n;
    cin >> n;
    double l = -1000, r = 1000;
    while (r - l > esp) {
        double mid = (l + r) / 2.0;
        if (mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    printf("%f", l);
    return 0;
}

标签:二分,满足条件,while,int,基础,mid,第一章,算法,区间
From: https://www.cnblogs.com/chenjq12/p/17114906.html

相关文章

  • 基于Astar算法的栅格地图目标最短路径搜索算法MATLAB仿真,带GUI界面
    1.算法描述       Astar算法是一种图形搜索算法,常用于寻路。它是个以广度优先搜索为基础,集Dijkstra算法与最佳优先(bestfit)算法特点于一身的一种算法。它通过......
  • 第一章 基础算法二
    高精度A+B:两个大整数相加A-B:两个大整数相减A×b:一个大整数乘一个小整数A÷b:一个大整数除以一个小整数大整数的存储:用一个数组来存大整数的每一位上的数。这......
  • 基于GA算法的TSP最短路径搜索matlab仿真
    1.算法描述(1)编码:将问题的候选解用染色体表示,实现解空间向编码空间的映射过程。遗传算法不直接处理解空间的决策变量,而是将其转换成由基因按一定结构组成的染色体。编码方......
  • 调度算法2
    调度算法21、时间片轮转调度算法(RR,Round-Robin)2、优先级调度算法非抢占式抢占式3、多级反馈队列调度算法知识回顾......
  • BF算法与KMP算法
    1.BF算法BF算法,即暴力(BruteForce)算法,是普通的【模式匹配】算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二......
  • Qt基础知识学习
    UI界面层(view)——>控制器层:当用户操作UI界面时,发射一个控制器层信号;控制器层(controller)——>模型层:控制层调用模型层功能函数,实现对应业务逻辑功能;模型层(model)——>控制器层......
  • 《分布式技术原理与算法解析》学习笔记Day09
    非集中式结构什么是非集中式结构?在非集中式结构中,服务的执行和数据的存储被分散到不同的服务器集群,服务器集群之间通过消息传递进行通信和协调,非集中式结构没有中央服务......
  • linux 基础(8)例行任务
    我们的linux系统,有时会自动进行线上更新,会定时升级locate用到的数据库。用户也会“在每天0点备份数据”或者“每天8点分析登录文件”,管理这些例行任务就叫做“工作调度”......
  • Java基础知识点(if语句的第二种和第三种)
    一:if语句的第二种格式1.格式:if(关系表达式){语句体1;​}else{语句体2;}2.执行流程:1.首先计算关系表达式的值。2.如果关系表达式的值为true,就执行语句体1.3.如果关系表达式的值......
  • 第一章-scala入门
    第1章Scala入门1.1概述1.1.1为什么学习Scala1)Spark—新一代内存级大数据计算框架,是大数据的重要内容。2)Spark就是使用Scala编写的。因此为了更好的学习Spar......