最近在刷一些java基础八股文,因此写一些文章记录一下,加深一下印象。
为啥要有二分查找或其他一些查找算法呢?假如说现在有一个数组[1,2,3,4,5]要查找一个5是否在这个数组中,这个时候大部分都会使用顺序查找也就是for循环来进行查找,这个时候只用查询5次就可以查找到我们所需要查找的元素5。
但是如果这个数组中的元素个数有成千上万的话,而且要找的元素5在数组中的最后一个,则需要查找的次数就为n次(n为数组的元素个数),这样的话查找的效率就比较低了,但是用二分查找或者其他一些查找算法的话则能大大提高查找的效率。
二分查找的思路二分查找的前提是当前的数组是有序的,因此如果是无序的数组要进行二分查找的话则需要先进行排序处理。二分查找的主要思想就是找到当前数组的中间值,再判断你要查找的值是大于小于还是等于这个中间值,然后再根据不同情况进行不同的操作。
假如说现在有一个长度为n的数组,而我们要查找的元素值为x,想查找在数组中是否存在该元素,这个时候的查找过程是这样的:
1.先给数组找一个左右边界,左边界left=0,有边界right=n-1
2.找到数组的中间值的索引,middle = (left + right) / 2。
3.判断x大于小于还是等于中间值
①如果x等于中间值的话,则返回中间值的索引middle
②如果x小于中间值的话,说明middle右边的值(包括middle索引对应的值)都是大于x的,这个时候我们就要重新设置右边界,右边界right=middle - 1,并重新查找
③如果x小于中间值的话,说明middle左边的值(包括middle索引对应的值)都是小于x的,这个时候我们就要重新设置左边界,左边界left=middle + 1,并重新查找
4.当左边界大于右边界的时候说明没有找到该元素,则退出循环。
二分查找图解结合上面的思路来进行一个简单的图解,假如有一个1-10的数组arr,这个时候我们要查找一个元素7,那么用二分查找是一个什么过程呢?如下图所示:
其中left表示左边界,right表示右边界,middle表示中间值的索引。
①第一次查找:
left = 0,right = 9,middle = (0 + 9) / 2 = 4(int向下取整,此处的left、right、middle皆为索引因此arr[middle] = arr[4] = 5)
这个时候,arr[middle]=arr[4]=5小于我们要查找的元素7,因此middle左边的值都不用看了因为都小于7,这个时候的左边界则为left=middle+1=5。
②第二次查找:
left = 5, right = 9, middle = (5 + 9) / 2 = 7
此时,arr[middle]=arr[7]=8,大于查找的元素7,这个时候middle右边的值都大于要查找的元素,这个时候右边界right=middle-1=6。
③第三次查找:
left=5,right=6,middle=(5+6)/2 = 5(int向下取整)
此时,arr[middle]=arr[5]=6,小于查找的元素7,则左边界left=middle + 1=6
④第四次查找:
left=6,right=6,middle=(6+6)/2 = 6
此时,arr[middle]=arr[6]=7,等于查找的元素7,这个时候就找到了我们要找的元素了,此时可以返回middle的索引了。
如果我们要查找的数组为[10,20,30,40,50,60,70,80,90,100]的话,而我们要查找的数为71的话,则会怎样,大家也可以自己画图模拟下。
二分查找的时间复杂度为O(logn),
顺序查找的时间复杂度为O(n)。
二分查找代码实现public class SearchUtils {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 7;
System.out.println(binarySearch(arr, target));
}
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (target == arr[middle]) {
return middle;
} else if (target > middle) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1; // 返回-1表示没找到
}
}
整数溢出问题
在上面的代码中还存在一个小缺陷,就是int middle = (left + right) / 2这行代码,如果left和right的数值很大,可能会超过int的取值范围导致整数溢出的问题,这个问题有两个解决办法:
1.公式转换
int middle = (left + right) / 2 = left / 2 + right / 2 = left - left / 2 + right / 2 = left + (right - left) /2
改良版代码如下:
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (target == arr[middle]) {
return middle;
} else if (target > middle) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1; // 返回-1表示没找到
}
2.使用移位运算符>>>
int midlle = (left + right) / 2 = (left + right) >>> 1
改良版代码如下:
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int middle = (left + right) >>> 1;
if (target == arr[middle]) {
return middle;
} else if (target > middle) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1; // 返回-1表示没找到
}
移位运算符简单理解:这里只讲举例正整数,比如说4用二进制来表示为0100,右移一位则为0010(2),因此对于正整数而言的话n>>>1等价于n / 2。(负数的话则不能保证),但由于索引只能为正整数,因此这里可以用这个>>>运算符。如果对于该运算符有疑问的话,可以参考下别的文章。



