(二十）查找算法-二分查找

1 基本介绍

二分查找又叫折半查找，是一种高效简单的查找算法，通常用于在有序的数组中查找某个元素，例如从{1,2,4,6,8,9,10,23,24}的数组中查找值是8的元素，就可以采用二分查找法。

二分查找的思想：
给一个有序的序列，取中间元素和目标元素进行对比，取其中的一半，丢弃另一半，快速缩小目标元素所在的位置。主要思想还是：快速缩小目标元素所在的区间。

二分查找的前置条件：

• 序列必须是有序的，升序或者降序都可以，这个条件主要是二分查找时需要和序列中的中间元素进行比较来排除一半的元素，如果是无序的，则比较无意义 。
• 序列必须是顺序存储元素的，顺序存储元素主要是可以快速的获取中间元素（可以通过索引），不然只能通过遍历来获取中间的元素，但是这种做法无意义，因为直接找该元素的时间复杂度为O（n），遍历获取中间元素再比较还不如直接查找。

二分查找的思路分析：

• 1.首先确定该数组的中间的下标 mid=(left+right)/2；
• 2.然后让需要查找的数 findVal 和 arr[mid] 比较；
  • 2.1 findVal > arr[mid]，说明要查找的数在 mid 的右边，因此需要递归的向右查找；
  • 2.2 findVal < arr[mid]，说明要查找的数在 mid 的左边，因此需要递归的向左查找；
  • 2.3 findVal = arr[mid]，说明找到，就返回；

思考：什么时候需要结束递归？
（1）找到就结束递归；
（2）递归完整个数组，仍然没有找到 findVal ，也需要结束递归，当 left > right 就需要退出。

图解：

2 代码实现

2.1 案例一

请对一个有序数组{1,8,10,89,1000,1234}进行二分查找，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就返回-1。
代码示例：

/*** 二分查找*/
public class BinarySearch {public static void main(String[] args) {// 使用二分查找的前提，数组是有序的int[] arr = {1, 8, 10, 89, 1000, 1234};int index = binarySearch(arr, 0, arr.length - 1, 88);System.out.println("index = " + index);}/*** 二分查找** @param arr     数组* @param left    左边的索引* @param right   右边的索引* @param findVal 要查找的值* @return*/public static int binarySearch(int[] arr, int left, int right, int findVal) {// 当 left > right 时，说明没有找到if(left > right){return -1;}int mid = (left + right) / 2;int midVal = arr[mid];// 向右递归if (findVal > midVal) {return binarySearch(arr, mid + 1, right, findVal);}else if (findVal < midVal) {// 向左递归return binarySearch(arr, left, mid - 1, findVal);}else {return mid;}}}

2.2 案例二

一个有序数组{1,8,10,89,1000,1000,1000,1234}，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000。
代码示例：

/*** 二分查找*/
public class BinarySearch {public static void main(String[] args) {// 使用二分查找的前提，数组是有序的int[] arr = {1, 8, 10, 89, 1000, 1000, 1000, 1234};ArrayList<Integer> list = binarySearch2(arr, 0, arr.length - 1, 1000);System.out.println(list);}/*** 思路分析：* 1. 在找到 mid 索引值，不要马上返回* 2. 向 mid 索引值的左边扫描，将满足条件的元素的下标，加入到集合* 3. 向 mid 索引值的右边扫描，将满足条件的元素的下标，加入到集合* 4. 将 ArrayList 返回*/public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {// 当 left > right 时，说明没有找到if (left > right) {return null;}int mid = (left + right) / 2;int midVal = arr[mid];// 向右递归if (findVal > midVal) {return binarySearch2(arr, mid + 1, right, findVal);} else if (findVal < midVal) {// 向左递归return binarySearch2(arr, left, mid - 1, findVal);} else {ArrayList<Integer> indexList = new ArrayList<>();// 向 mid 索引值的左边扫描int temp = mid - 1;while (true) {if (temp < 0 || arr[temp] != findVal) {break;}indexList.add(temp);// 左移temp--;}indexList.add(mid);temp = mid + 1;while (true) {if (temp > arr.length - 1 || arr[temp] != findVal) {break;}indexList.add(temp);// 右移temp++;}return indexList;}}}