数据结构 -- 二分查找

本文主要梳理了二分查找算法的几种实现思路，基本概念参考 顺序、二分、哈希查找的区别及联系_生成一个大小为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]与target3.循环内的平均比较次数减少了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;elsereturn 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;}
}

运行结果