如何使用Java二分查找(java,编程语言)

基本思想：又叫折半查找，要求待查找的序列有序，是一种快速查找算法，时间复杂度为 O(logn)，要求数据集为一个有序数据集。

应用场景：一般用于查找数组元素，并且数组在查找之前必须已经排好序(一般是升序)。

步骤：

1、取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，

2、如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。

3、直到查找到了为止，否则序列中没有待查的关键字。

代码示例：

基本思想：比较前后相邻的两个数据，如果前面数据大于后面的数据，就将这二个数据交换。这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第 N-1 个位置。N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。

应用场景：数据量不大，对稳定性有要求，且数据基本有序的情况。

步骤：

1、将序列中所有元素两两比较，将最大的放在最后面。

2、将剩余序列中所有元素两两比较，将最大的放在最后面。

3、重复第二步，直到只剩下一个数。

代码示例：

基本思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

应用场景：数据量不大，对算法的稳定性有要求，且数据局部或者整体有序的情况。

步骤：

1、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。)

代码示例：

基本思想：选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的)，比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。

应用场景：数值范围较大，相同值的概率较小，数据量大且不考虑稳定性的情况，数值远大于数据量时威力更大。

步骤：

1、一次循环，从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。

2、找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。

3、直到从前往后的比较索引 > 从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

代码示例：

基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

应用场景：数据量较大，不要求稳定性的情况。

步骤：

1、选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1;

2、按增量序列个数 k，对序列进行 k 趟排序;

3、每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码示例：

基本思想：归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

应用场景：内存少的时候使用，可以进行并行计算的时候使用。

步骤：

1、选择相邻两个数组成一个有序序列。

2、选择相邻的两个有序序列组成一个有序序列。

3、重复第二步，直到全部组成一个有序序列。

代码示例：

基本思想： 把数组 arr 划分为 n 个大小相同子区间(桶)，每个子区间各自排序，最后合并 。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

应用场景：在数据量非常大，而空间相对充裕的时候是很实用的，可以大大降低算法的运算数量级。

步骤：

1、找出待排序数组中的最大值 max、最小值 min

2、我们使用动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1

3、遍历数组 arr，计算每个元素 arr[i] 放的桶

4、每个桶各自排序

代码示例：

基本思想：将所有待比较数值(正整数)统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

应用场景：用于大量数，很长的数进行排序时的情况。

步骤：

1、将所有的数的个位数取出，按照个位数进行排序，构成一个序列。

2、将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。

代码示例：

基本思想：在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。

应用场景：通常应用在 DFS 和 BFS 搜索算法中，寻找过滤条件，提前减少不必要的搜索路径。

步骤：

1、基于训练数据集生成决策树，生成的决策树要尽量大;

2、用验证数据集最已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准

代码示例：

基本思想：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

应用场景：设置一个递归函数，函数的参数会携带一些当前的可能解的信息，根据这些参数得出可能解或者不可能而回溯，平时经常见的有 N 皇后、数独、集合等情况。

步骤：

1、定义一个解空间，它包含问题的解;

2、利用适于搜索的方法组织解空间;

3、利用深度优先法搜索解空间;

4、利用限界函数避免移动到不可能产生解的子空间。

代码示例：

基本思想：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA 算法等。

应用场景：应用有计算机网络路由算法，机器人探路，交通路线导航，人工智能，游戏设计等。

步骤：(Dijkstra 算法示例)

1、 访问路网中里起始点最近且没有被检查过的点，把这个点放入 OPEN 组中等待检查。

2、 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到 CLOSE 表中。

3、 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到 OPEN 表中。

4、重复2，3，步。直到 OPEN 表为空，或找到目标点。

代码示例：

基本思想：给定一个整数数组 nums ，找到一个具有最大和的连续子数组(子数组最少包含一个元素)，返回其最大和。

应用场景：生活中可以用来查看股票一周之内的增长状态，需要得到最合适的买入和卖出时间。

步骤：

1、将子串和为负数的子串丢掉，只留和为正的子串。

2、如果 nums 中有正数，从左到右遍历 nums，用变量 cur 记录每一步的累加和，遍历到正数 cur 增加，遍历到负数 cur 减少。

3、当 cur>=0 时，每一次累加都可能是最大的累加和，所以，用另外一个变量 max 全程跟踪记录 cur 出现的最大值即可。

代码示例：

基本思想：最长公共子序列是一个在一个序列集合中用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置。

应用场景：最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如 Diff 工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如 Git 用来调和文件之间的改变。

步骤：

1、可以使用递归去解决，需要遍历出所有的可能，很慢;

2、对于一般的 LCS 问题，都属于 NP 问题;

3、当数列的量为一定的时，都可以采用动态规划去解决。

代码示例：

基本思想：在含有n个顶点的带权无向连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树(不一定唯一)。

一般情况，要解决最小生成树问题，通常采用两种算法：Prim算法和Kruskal算法。

应用场景：一般用来计算成本最小化的情况。

步骤：(Prim 算法示例)

1、以某一个点开始，寻找当前该点可以访问的所有的边;

2、在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边;

3、寻找当前集合可以访问的所有边，重复 2 的过程，直到没有新的点可以加入;

4、此时由所有边构成的树即为最小生成树。

代码示例：