查找算法
常用的查找算法有：
- 顺序（线性）查找
- 二分查找（折半查找）
- 插值查找
- 斐波那契查找
1、二分查找算法
1.1 二分查找思路分析
二分查找的条件：
- 查找的数量只能是一个，从指定一组数据中查找一个需要的数据
- 二分查找用于查找的数据，逻辑上应该是有序的
因为数组时有序的，首先找到要查找的数组中间位置的下标
然后将要查找的数和
arr[mid]数组中间位置的值进行比较如果要找的数与中间数相等，就返回
如果要查找的数在中间数的左边，向左递归进行查找，在右边就向右递归进行查找
如果递归完整个数组仍未找到要找的数，结束递归退出
1.2 二分查找代码实现
给定一个数组内元素有序的数组，通过二分查找找到需要查找的数的位置，如果值存在返回下标，否则返回 -1
下面数组中所有元素是不重复的
public static void main(String[] args) {
int[] arr = {
1,3, 5, 32, 34, 234};
int i = binarySearch(arr, 0, arr.length - 1, 34);
System.out.println(i);
}
/**
* 二分查找算法
* @param arr 数组
* @param left 左边的索引
* @param right 右边的索引
* @param finalVal 要查找的值
* @return 找到返回下标，未找到返回 -1
*/
public static int binarySearch(int[] arr, int left, int right, int finalVal) {
int mid = (left + right) / 2; // 找到中间位置 mid
int midValue = arr[mid]; // 中间位置的值 midValue
// 左边下标大于右边，返回 -1
if (left > right) {
return -1;
}
// 看要查找的值在中间位置值的左边还是右边，进行递归。如果中间值为要查找的值则返回
if (finalVal > midValue) {
return binarySearch(arr, mid + 1, right, finalVal);
} else if (finalVal < midValue) {
return binarySearch(arr, left, mid - 1, finalVal);
} else {
return mid;
}
}