递归二分查找java

1. java基础语法部分有哪些

Java的基础语法包括：
1. 开发环境搭建
2. 常量
3. 变量
4. 数据类型
5. 运算符
6. 选择结构-if-switch
7. 循环结构-while-【do-while】-for以及各种循环控制与多层嵌套循环
8. 方法的设计与使用
9. 数组
10. 递归
11. 冒泡-选择等多种排序
12. 二分查找
13. 线性查找

2. java二分法查找的递归算法怎么实现

什么是二分查找？

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找优缺点

优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
使用条件：查找序列是顺序结构，有序。

过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

利用循环的方式实现二分法查找

public class BinarySearch {
public static void main(String[] args) {
// 生成一个随机数组 int[] array = suiji();
// 对随机数组排序 Arrays.sort(array);
System.out.println("产生的随机数组为： " + Arrays.toString(array));

System.out.println("要进行查找的值： ");
Scanner input = new Scanner(System.in);
// 进行查找的目标值 int aim = input.nextInt();

// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);

}

/** * 生成一个随机数组 *
* @return 返回值，返回一个随机数组 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之间的随机数 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循环遍历为数组赋值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}

/** * 二分法查找 ---循环的方式实现 *
* @param array 要查找的数组 * @param aim 要查找的值 * @return 返回值，成功返回索引，失败返回-1 */
private static int binarySearch(int[] array, int aim) {
// 数组最小索引值 int left = 0;
// 数组最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围 if (aim < array[mid]) {
right = mid - 1;
// 若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找数据与中间元素值正好相等，则放回中间元素值的索引 } else {
return mid;
}
}
return -1;
}}
运行结果演示：

总结：

递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~

3. <算法图解>

二分查找、大O分析法；数组和链表；递归、快速排序；分治、动态规划、贪婪算法；散列表（键值对组成的数据结构）；图算法（模拟网络的方法）：广度优先搜索、迪杰斯特拉算法（计算网络中两点之间最短距离）；K近邻（KNN，用于创建推荐系统、OCR引擎、预测股价、物件分类）。

二分查找的时间复杂度为log2n，多少个2相乘等于n。

有序数组，定义low和high，非一个元素，猜中，大了，小了。

选择排序：o(n方)，快速排序：o(nlogn)，存储最小的值，存储最小元素的索引，找出最小的值，加到新数组中。

循环，程序的性能更好，递归，程序更容易理解。栈有两种操作：压入和弹出。

每个递归函数都有两部分：基线条件和递归条件，递归条件指的是函数调用自己，基线条件指的是函数不再调用自己，避免无限循环。

编程概念，调用栈，计算机在内部使用被称为调用栈的栈，递归是调用自己的函数。

调用栈可能占用大量内存，解决方案是编写循环代码，或者使用尾递归，但并非所有的语言都支持尾递归。

分治-递归式问题解决办法：步骤：找出基线条件，确定如何缩小问题的规模，使其符合基线条件。

涉及数组的递归函数，基线条件通常是数组为空或只包含一个元素。

快速排序-D&C算法：步骤：设置基线条件，数组小于2，选择基准值，将数组分成两个子数组：小于和大于基准值的元素，对这两个子数组进行快速排序，递归调用。

合并排序：o(nlogn)，快速排序：o(nlogn)：层数o(logn)乘每层需要的时间o(n)，但最差情况为o(n方)。

散列表-基本数据结构之一：内部机制：实现、冲突、散列函数。

散列表无序，数据结构：数组、列表、（栈、不能用于查找）、散列表（包含额外逻辑）。

数组和链表都直接映射到内存，但散列表使用散列函数来确定元素存储位置。

散列函数：不同的输入映射到不同的索引，输出不同的数字，散列表是散列函数和数组的结合，也称散列映射、映射、字典、关联数组。

缓存的数据存储在散列表中，访问页面时，先检查散列表是否存储了页面。

如果两个键映射到了同一个位置引发冲突，可以在这个位置存储一个链表，好的散列函数可以减少冲突。

填装因子为散列表元素/位置总数，因子越低，发生冲突的可能性越小，性能越高。

广度优先搜索（BFS）的含义：解决最短路径问题的算法。

步骤：使用图来建立问题模型，使用广度优先搜索算法（是否有路径，哪个路径最短）。

所有算法中，图算法是最有用的。

队列（数据结构）：类似于栈，不能随机访问队列中元素，只支持入队和出队（压入和弹出），先加入的先出队，即先进先出（FIFO），而栈是后进先出（LIFO）。

有向图：关系是单向的，无向图：没有箭头，直接相连的节点互为邻居。

拓扑排序：根据图创建一个有序列表。

迪杰斯特拉算法：适用于加权图（提高或降低某些边的权重），找出加权图中的最短路径。

只适用于有向无环图，如果有负权边，不能使用迪杰斯特拉算法，因为算法假设处理过的节点，没有前往终点的最短路径，故，有负权边的可用贝尔曼-福特算法。

在未处理的节点找到开销最小的节点，遍历当前节点的所有邻居，如果经当前节点前往该邻居更近，就更新邻居开销，同时将该邻居的父节点设置为当前节点，将当前节点标记为处理过，找出接下来要处理的节点，并循环。

贪婪算法：每步都选择局部最优解，最终就是全局最优解，易于实现，运行快，是个不错的近似算法。

集合类似于列表，但是不包含重复的元素。

贪婪算法：o(n方)，NP完全问题：需要计算所有的解，从中选出最小距离，计算量大，最佳做法是使用近似算法。

动态规划：约定条件下找到最优解，在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。

动态规划解决方案涉及网络，每个单元格都是子问题，需考虑如何将问题分解为子问题。

最长公共序列。

K最近邻算法（KNN）：电影推荐系统。

特征抽取：指标打分，计算距离（相似程度），N维。

KNN的基本工作：分类和回归。

应用：OCR光学字符识别（optical character recognition），提取线段、点、曲线特征，找出与新图像最近的邻居；语音识别，人脸识别。

垃圾邮件过滤器：朴素贝叶斯分类器。

二叉查找树（binary search tree）：有序树状数据结构。

二叉查找树插入和删除操作快于有序数组，但不能随机访问（没有索引）。

红黑树是处于平衡状态的特殊二叉树，不平衡时，如向右倾斜时性能不佳。

B树是一种特殊的二叉树。

反向索引：一个散列表，将单词映射到包含他的页面，常用于创建搜索引擎。

并行算法：速度的提升非线性，因为并行性管理开销和负载均衡。

分布式算法：特殊的并行算法，maprece（映射和归并函数），映射：任务多时自动分配多台计算机完成，将一个数组转换成另一个数组，归并是将一个数组转换成一个元素。

线性规划：在给定约束条件下最大限度的改善指定指标，使用simplex算法，图算法为线性规划子集。