二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
代码实现：
public class BinarySearchByRecursion {
public static void main(String[] args) {
int[] sortedArr = { 1, 3, 5, 8, 10, 12 };
System.out.println(binarySearch(sortedArr, 10));
System.out.println(binarySearchByRecursion(sortedArr, 0, sortedArr.length - 1, 10));
//JDK提供二分查找算法
System.out.println(Arrays.binarySearch(sortedArr, 10));
}
/**
* 非递归二分查找算法
*
* @param srcArray
* 有序数组
* @param des
* 待查找数据
* @return 返回-1 未找到
*/
public static int binarySearch(int[] srcArray, int des) {
int low = 0;// 第一个位置
int high = srcArray.length - 1;// 最高位置.数组长度-1,因为下标是从0开始的
while (low <= high) {// 循环终止条件是low不大于high
// int middle = low + ((high - low) >> 1);
int middle = (low + high) >> 1;// 左移1位=除2
if (des == srcArray[middle]) {// 与最中间的数字进行判断,是否相等,相等的话就返回对应的数组下标
return middle;
} else if (des < srcArray[middle]) {
// 移动high
high = middle - 1;
} else if (des > srcArray[middle]) {
// 移动
low = middle + 1;
}
}
return -1;
}
/**
* 递归方式实现
*
* @param srcArray
* @param low
* @param high
* @param des
* @return
*/
public static int binarySearchByRecursion(int[] srcArray, int low, int high, int des) {
if (low <= high) {
int middle = (low + high) >> 1;
if (des == srcArray[middle]) {// 与最中间的数字进行判断,是否相等,相等的话就返回对应的数组下标
return middle;
} else if (des < srcArray[middle]) {
// 移动high
return binarySearchByRecursion(srcArray, low, middle - 1, des);
} else if (des > srcArray[middle]) {
// 移动
return binarySearchByRecursion(srcArray, middle + 1, high, des);
}
}
return -1;
}
}
