下载文档原格式
二分思想的应用二分是我们再熟悉不过的字眼了，计算机科学由于其特殊性更是与“2”结下了不解之缘。
尽管二分思想本身很简单，但它的扩展性之强，应用面之广，仍然很有研究的价值．下面从最简单的二分查找开始逐步探究二分思想在信息学竞赛中的应用．一、二分查找问题如下：给定一个有序的数组，查找k是否在数组中。
分析：首先，将表中间位置记录的关键字与k比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表．重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功．容易知道算法的时间复杂度为O（logN）。
★好感统计（star.pas/c/cpp）[问题描述]在LazyCat同学的影响下，Roby同学开始听伊拉克的音乐，并且越来越喜欢萨达姆，尤其喜欢卡尔扎伊和Tony．可是，爱学习爱思考的Roby同学想，如果以后喜欢的伊拉克歌手越来越多怎么办呢?Roby怎么知道Roby最喜欢谁呢(Roby不知道谁知道呢……)?于是，goby同学求助于你．Roby首先会给你一张表，表上是所有他认识的伊拉克歌手的名字，一开始他对所有伊拉克歌手的好感度都为0。
然后RobY会告诉你一些他对某个伊拉克歌手的好感度变化．最后，请按照Roby对伊拉克歌手好感从大到小的顺序输出他们．[输入文件]输入文件star．in的第一行有一个整数N，表示Roby知道的伊拉克歌手数目．下面有N行，表示每一个Roby认识的伊拉克歌手的名字．接下来一行有一个整数K．再下面有2*K行，每两行为一组，上面一行为伊拉克歌手的名字Name，下面一行为一个整数，表示好感度变化量Change．[输出文件]输出文件star.out包括N*2行，依据伊拉克歌手们受RobY的好感度从大到小的顺序输出，每两行为一组，第一行输出伊拉克歌手的名字，第二行输出受Roby的好感度，[样例输入]3HhlsaGayZcLoveStudyTony5ZcLoveStudy100Tony8888ZcLoveStudy20Tony8888HhlsaGay-1000[样例输出]Tony17776ZcLoveStudy120HhlsaGay-1000[数据范围]对于40％的数据，保证N≤3000，K≤30000。
二分算法知识点一、知识概述《二分算法知识点》①基本定义：二分算法嘛，简单说就是一种在有序数据里找东西的办法。
就像你在一串按大小排好序的数字里找一个特定的数字。
每次都把这个有序的范围分成两部分，然后看看要找的东西是在左边那部分还是右边那部分，不断缩小这个范围，直到找到那个东西或者确定没有这个东西了。
②重要程度：在计算机科学里，这是个挺重要的算法呢。
不管是查找东西还是解决一些优化问题，经常会用到。
比如说查字典（当然这里夸张点类比，字典本身没有用二分法查找，但是这个查找思路类似），如果字典的单词是按照字母顺序排好的，二分法就好像你每次能快速定位到你要找的单词可能在的那一大部分页码，比一页一页翻可有效率多了。
③前置知识：得知道基本的顺序结构这些编程概念吧，如果是从数学角度理解，至少要知道大小比较，数据排序这些简单的知识。
因为二分法依赖于数据是有序的这个前提。
④应用价值：在很多数据查询系统里都会用到，就像在一个很大的学生成绩数据库里按照成绩排名查找某个特定分数段的学生，用二分算法就很快了。
在计算机游戏里查找某个合适的难度配置可能也会用到它，找到合适玩家的难度，让游戏玩起来既不会太简单又不会太难。
二、知识体系①知识图谱：在算法这部分知识里，二分算法是挺基础的查找和优化算法那一组的。
它依赖于数据结构里元素有序的部分知识。
②关联知识：和排序算法关系密切，因为二分算法要想正确运用，数据首先得是有序的。
跟查找有关的其他算法也有关联，像顺序查找，二分算法就是一种效率更高的查找改进。
③重难点分析：掌握难点在于那个范围一分为二之后的选择，到底是选左边还是右边部分继续。
关键是对数据有序这个概念要理解得透彻，还有每次分割范围时候边界的处理要很小心。
④考点分析：在计算机相关课程或者算法课程的考试里，如果有算法考核，这是个很基础的考点。
可能会出选择填空考考你对基本原理的理解，也可能让你写个简单的代码来实现二分查找给定数组里的某个元素这样的题目。
二分法计算点集最近的两个点及距离文章标题：探讨二分法在计算点集中最近的两个点及其距离中的应用在计算机科学和算法领域中，二分法是一种非常常见且有效的算法，它在许多问题的解决中发挥着重要作用。
其中，二分法在计算点集中最近的两个点及其距离时，也有着极其重要的应用。
本文将深入探讨二分法在这一问题中的应用，从简单到复杂、由浅入深地介绍二分法的原理，探讨其在计算最近点对时的实际应用，并分享一些个人观点和理解。
一、什么是二分法让我们简要介绍一下二分法的基本原理。
二分法，英文名为Binary Search，是一种在有序数组中查找特定元素的搜索算法。
其基本原理是每次将待查找区间对半分，然后确定要查找的值在哪一半，从而缩小查找范围，直到找到要查找的值或确定值不存在为止。
二、二分法在计算最近点对中的应用在计算最近点对的问题中，给定一个包含n个点的集合，需要找到集合中距离最近的两个点，并计算它们的距离。
对于这一问题，我们可以借助二分法来解决。
具体而言，我们可以首先根据点的横坐标对点集进行排序，然后利用二分法在排好序的点集中寻找最近点对。
由于排好序的点集在空间中具有一定的顺序关系，因此可以利用这一特性来优化查找过程，从而减少计算量。
在利用二分法查找最近点对时，我们可以将点集等分成两部分，然后分别在左右两部分中寻找最近点对。
然后再考虑中间部分的情况，这样就可以递归地求解最近点对的问题。
通过不断地将点集分割、计算和比较，最终可以找到整个点集中最近的两个点，并计算它们的距离。
三、二分法在计算最近点对中的实际应用二分法在计算最近点对的算法中有着广泛的实际应用价值。
通过巧妙地利用二分法，可以在较快的时间内找到点集中最近的两个点，并计算它们的距离。
这对于许多计算机图形学、空间数据分析等领域都具有重要意义。
在实际应用中，我们可以结合二分法和分治法来处理最近点对的问题，从而提高算法的效率和精度。
通过合理地设计算法流程和数据结构，可以使二分法在计算最近点对问题中发挥出色的效果。
计算几何中的二分思想——贵阳市第一中学程芃祺【摘要】本文简要阐述了计算几何中的二分思想，并通过例题对其进行应用，体现二分在计算几何中简洁高效的优势。
【关键字】计算几何二分【引言】二分思想，古已有之，邵子曰：“一分为二，二分为四，四分为八也。
”正是根据这样的思想，我们的祖先创造了太极八卦。
在当今的信息时代中，这一古老的智慧依旧闪耀着光芒，通过渗透到各门新兴学科中发扬光大，计算几何学就是其中之一。
在此基础上，产生了无数经典算法，例如用分治法求解最近点对、凸包、三角剖分和空间分区二叉树。
在近年来的各类信息学竞赛中，不断涌现了大批关于计算几何的试题，其中许多复杂的题目可以利用二分思想得到简单解决。
掌握了这一思想，无疑是多了一把解决相关问题的利器。
【例题解析】下面，就让我们通过几个例题，一起探究二分思想的应用。
例题一、Simplified GSM Network ( 2005 ACM/ICPC World Finals )题意：已知B（1≤B≤50）个信号站和C（1≤C≤50）座城市的坐标，坐标的绝对值不大于1000，每个城市使用最近的信号站。
给定R（1≤R≤250）条连接城市线路的描述和Q（1≤Q≤10）个查询，求相应两城市间通信时最少需要转换信号站的次数。
分析：显然，题目要求的是最短路，关键在于线路权值的计算。
题目中告诉我们：每个城市使用最近的信号站，也就是说，该城市所处位置位于平面中离这一信号站最近的点的轨迹内，而离各点最近点的轨迹就是V oronoi图。
因此，每条路线的权值就是这条线段所穿过的V oronoi边的数量。
由上可看出，题目即为求V oronoi图与最短路的简单组合，只需分别解决。
通过以上的分析，我们发现了一种最直接的办法：先求V oronoi图，再求最短路。
此法时间效率也足以通过测试，可是求V oronoi图的编程复杂度很高、调试麻烦，在真实的竞赛环境中实用性不强。
有没有更好一点的解法呢？考虑一条线段l，如果l两端点所属的信号站相同，显然l的权值为零，否则将l从中点（红点）分为两部分（分割点不在V oronoi边上）l1和l2，l所对应的权值自然就等于l1和l2的权值之和。
