二分查找算法思想
二分查找顾名思义就是分成两半查找，但是这个查找需要有一个前提是：这个数组必须是有序的，具体实现：二分之后的数与要查找的数比较如果相等直接返回；如果大于要查找的数，就在小的那部分查找；如果小于要查找的数就在大的那部分查找。
二分查找算法实现
public static void main(String[] args) {
int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};
//先排序
int[] insertSort = InsertSort.insertSort(arr);
//二分查询
int result1 = binarySearch(insertSort, 5);
int result2 = binarySearchTwo(insertSort, 0, insertSort.length, 5);
System.out.println(result1 == result2);
}
/**
* 二分查找【非递归实现】
*
* @param insertSort 排完序的数组
* @param key 需要查找的key
* @return
*/
private static int binarySearch(int[] insertSort, int key) {
if (insertSort.length == 0) return -1;
int low = 0;
int high = insertSort.length - 1;
while (low <= high) {
int mid = (high + low) / 2;
if (insertSort[mid] == key) {
return mid;
} else if (insertSort[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
/**
* 二分查找【递归实现】
*
* @param insertSort 排完序的数组
* @param key 需要查找的key
* @return
*/
private static int binarySearchTwo(int[] insertSort, int low, int high, int key) {
if (low > high) return -1;
int mid = (high + low) / 2;
if (insertSort[mid] == key) return mid;
else if (insertSort[mid] < key) {
return binarySearchTwo(insertSort, mid + 1, high, key);
} else {
return binarySearchTwo(insertSort, low, mid - 1, key);
}
}
递归和非递归的实现代码都贴出来了，整体来说思想还是比较简单，想看完成版源码请点击：二分查找
