算法原理
二分查找也称折半查找(Binary Search)，它是一种效率较高的查找方法。折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分查找的思想：在一个长度为n的有序数组中查找值等于m的元素位置，先取数组中间位置 mid 的元素与其相比。如果值等于 m 则返回 mid 值，小于 m 则在数组 0 至 mid-1 区间上按照此方法继续比较查找，大于 m 则在数组 mid + 1 至 n 区间上按照此方法继续比较查找。
时间复杂度
假设总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（操作元素的剩余个数），其中k就是循环的次数。
由于 n/2^k 取整后>=1，即令n/2^k=1
可得k=log2n（是以2为底，n的对数），所以时间复杂度表示为O(logn)
空间复杂度
二分查找占用空间非常小，额外使用了几个临时变量如left、right、mid，因此其空间复杂度为O(1)
动图演示
示例: 从一组有序数组[1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]中查询值为37的索引下标
演示.gif
代码实现
二分查找非递归方式代码：
/**
* 二分查找(非递归方式)
*
* @param arr 有序数组
* @param num 查找元素值
* @return boolean
*/
public static int find(int[] arr, int num) {
if (arr == null || arr.length == 0) {
return -1;
}
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == num) {
return mid;
} else if (arr[mid] < num) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
二分查找递归方式代码：
/**
* 二分查找(递归方式)
*
* @param arr 有序数组
* @param num 查找元素值
* @return boolean
*/
public static int find(int[] arr, int left, int right, int num) {
if (arr == null || arr.length == 0 || left > right) {
return -1;
}
int mid = (left + right) / 2;
if (arr[mid] == num) {
return mid;
} else if (arr[mid] < num) {
return find(arr,left + 1, right, num);
} else {
return find(arr,left + 1, right, num);
}
}
测试代码：
public static void main(String[] args) {
int[] array = new int[] {1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
System.out.println("二分查找非递归方式: " + find(array, 37));
System.out.println("二分查找递归方式: " + find(array, 0, array.length - 1, 37));
}
结语
感谢您的阅读，请动动您可爱的小手✌~点赞，留言，关注，分享 4暴击(∩_∩)
