本文主要梳理了二分查找算法的几种实现思路,基本概念参考 顺序、二分、哈希查找的区别及联系_生成一个大小为10万的有序数组,随机查找一个元素,分别采用顺序查找和二分查找方式-CSDN博客
1、基本概念
(1)前提条件:待查找数据必须有序。
(2)实现方式:在查找过程中,它先和中间的比较,如果等于就直接返回,如果小于就在前半部分继续使用二分法进行查找,如果大于则在后半部分继续使用二分法进行查找。
2、算法实现
2.1 基本版实现
package com.hh.algorithm.find;
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1,2,4,5,5,6,7,8,9,11,23};
System.out.println(BinarySearch.binary(arr, 4));
}
public static int binary(int[] arr, int key) {
int i = 0;
int j = arr.length - 1;
while (i <= j) {
int mid = (i + j) >>> 1;
if (key < arr[mid]) {
j = mid - 1;
} else if (key > arr[mid]) {
i = mid + 1;
} else {
return mid;
}
}
return -1;
}
}
问题1:为什么是 i<=j ,而不是 i<j?
(1)i==j:意味着 i,j 它们指向的元素也会参与比较;
(2)i<j:只意味着mid 指向的元素参与比较。
问题2:j - ((j - i) >> 1) 与 (i+j)/2都是相加除2,使用后者有没有问题?
当超出 int 的范围时,他会把最高位视为符号位。
代码实现
package com.hh.algorithm.find;
public class BinarySearchTest {
public static void main(String[] args) {
/*
同一个二进制数
1011 1111 1111 1111 1111 1111 1111 1110
没有超出int 范围,默认是:不把最高位视为符号位,代表3221225470
超出int 范围,把最高位视为符号位,代表-1073741826
所以,当计算结果超出int的范围时,他就会把最高位视为符号位
*/
int i = 0;
int j = Integer.MAX_VALUE - 1;
int mid = (j + i) / 2;
int mid2 = (i + j) >>> 1;
System.out.println("第1轮(j + i) / 2:" + mid);
System.out.println("第1轮(j+i)/2:" + mid2);
System.out.println("---------------------");
i = mid+1;
mid = (j + i) / 2;
mid2 = (i + j) >>> 1;
System.out.println("第2轮(j + i) / 2:" + mid);
System.out.println("第2轮(j+i)/2:" + mid2);
/*
扩展:
(1)(j + i) / 2还有另一种写法,也就是 j - (j - i) / 2
(2)j - (j - i) / 2 拆开就是 j - j/2 + i/2 --> j/2 + i/2 --> (j + i) / 2
*/
}
}
运行结果
2.2 平衡版实现
package com.hh.algorithm.find;
/*
// 如果待查找数字一直在左边,if那么就会判断比较log(n)次
if (key < arr[mid]) {
j = mid - 1;
} else if (key > arr[mid]) {
// 如果待查找数字一直在右边,if那么就会判断比较2log(n)次
i = mid + 1;
} else {
return mid;
}
解决方式:
1.左闭右开的区间,i指向的可能是目标,而j指向的不是目标
2.不在循环内找出,等范围内只剩i时,退出循环,在循环外比较 a[i]与target
3.循环内的平均比较次数减少了
4.时间复杂度 θ(log(n))
*/
public class BinarySearch2 {
public static void main(String[] args) {
int[] arr = {1,2,4,5,5,6,7,8,9,11,23};
System.out.println(BinarySearch2.binary(arr, 4));
}
public static int binary(int[] arr, int key) {
int i = 0;
int j = arr.length;
while (i + 1 < j) {
int mid = (i + j) >>> 1;
if (key < arr[mid]) {
j = mid;
} else{
i = mid;
}
}
return (key == arr[i])? i : -1;
}
}
运行结果
2.3 java版实现
package com.hh.algorithm.find;
/**
* 下面是java版本的二分查找代码实现,粘贴了底层代码
*/
public class BinarySearch3 {
public static void main(String[] args) {
int[] arr = {1,2,4,5,5,6,7,8,9,11,23};
System.out.println(BinarySearch3.binarySearch(arr,4));
}
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
//没找到就返回插入点位置
return -(low + 1); // key not found.
}
}
运行结果
2.4 有重复元素的数组,返回左右
package com.hh.algorithm.find;
/**
* 当该数组有重复元素时,返回最靠左(右)的元素位置
*/
public class BinarySearchMost {
public static void main(String[] args) {
int[] arr = {1,2,4,5,7,7,7,7,11,23};
System.out.println(BinarySearchMost.binaryLeft(arr,7));
System.out.println(BinarySearchMost.binaryRight(arr,7));
}
/*
返回最靠左的元素索引
*/
public static int binaryLeft(int[] arr, int key) {
int i = 0;
int j = arr.length - 1;
int candidate = -1;
while (i <= j) {
int mid = (i + j) >>> 1;
if (key < arr[mid]) {
j = mid - 1;
} else if (key > arr[mid]) {
i = mid + 1;
} else {
candidate = mid;
j = mid -1;
}
}
return candidate;
}
/*
返回最靠右的元素索引
*/
public static int binaryRight(int[] arr, int key) {
int i = 0;
int j = arr.length - 1;
int candidate = -1;
while (i <= j) {
int mid = (i + j) >>> 1;
if (key < arr[mid]) {
j = mid - 1;
} else if (key > arr[mid]) {
i = mid + 1;
} else {
candidate = mid;
i = mid +1;
}
}
return candidate;
}
}
运行结果
2.5 没找到返回有意义的值
package com.hh.algorithm.find;
/**
* 当该数组找不到该元素时,返回大于(小于)等于目标的最靠左(右)的索引位置
*/
public class BinarySearchMost2 {
public static void main(String[] args) {
int[] arr = {1,2,4,5,7,7,7,7,11,23};
System.out.println(BinarySearchMost2.binaryLeft(arr,3));
System.out.println(BinarySearchMost2.binaryRight(arr,9));
}
/*
返回大于目标的最靠左索引
*/
public static int binaryLeft(int[] arr, int key) {
int i = 0;
int j = arr.length - 1;
while (i <= j) {
int mid = (i + j) >>> 1;
if (key <= arr[mid]) {
j = mid - 1;
} else{
i = mid + 1;
}
}
return i;
}
/*
返回最小于目标的最靠右索引
*/
public static int binaryRight(int[] arr, int key) {
int i = 0;
int j = arr.length - 1;
while (i <= j) {
int mid = (i + j) >>> 1;
if (key < arr[mid]) {
j = mid - 1;
} else {
i = mid +1;
}
}
return i-1;
}
}
运行结果
本文为学习笔记,所参考文章均已附上链接,若有疑问请私信!
创作不易,如果对你有点帮助的话麻烦点个赞支持一下!
新手小白,欢迎留言指正!