1.二分查找是什么？
二分查找也称折半查找，是一种效率较高的查找方式。但是，二分查找要求线性表为顺序存储结构且表按关键字有序排列。
时间复杂度：O（log2n）
2.二分查找的思路分析
便于叙述，笔者以数组array[N] = [1,10,20,30,99,1020]为例。left、right分别表示数组的左界和右界。需要查找的值记为value。
首先，我们需要确定数组中间的下标（位置）：mid = （left+right）/2;
将需要查找的数value与array[mid]比较：
（1）若value > array[mid]：说明需要查找的数在mid的右边，需要更新left、mid值向右侧查找；
（2）若value < array[mid]: 说明需要查找的数在mid的左边，需要更新right、mid值向左侧查找；
（3）若value = array[mid]： 说明找到了需要查找的数，返回位置值即可。
3.思路图解
假设我们需要查找数值99，mid首先指向的位置应为20的位置。left指向1，right指向1020。判断array[mid] = 20 与 99 不相等，此时，left = mid + 1，右移；right 不变；mid更新为4。此时，array[mid] = 99, 查找成功，返回索引值4。
4.代码实现（递归方式）
何时递归结束？？？
找到value，返回mid；
没有找到value：此时整个数组已经被递归搜索完成，left > right，结束递归，并且返回-1(认为没有匹配值)。
具体Java代码实现如下：
public class BinarySearch { public static void main(String[] args) { int[] array = {1,10,20,30,99,1020}; // 待查找值设置为99 、 0 int value1 = 99; int value2 = 0; System.out.println(value1 + "'s index: " + bs(array,0,array.length-1,value1)); System.out.println(value2 + "'s index: " + bs(array,0,array.length-1,value2)); } // 二分查找递归实现 /** * * @param array 数组 * @param left 左端点 * @param right 右端点 * @param value 待查找的值 * @return 查找到value则返回索引值；否则返回-1 */ public static int bs(int[] array, int left, int right, int value) { // 没有找到 if(left > right){ return -1; } int mid = (left + right) / 2; if(value > array[mid]){ // 向右查找,更新left = mid + 1 return bs(array, mid + 1, right, value); }else if(value < array[mid]){ // 向左查找,更新right = mid - 1 return bs(array, left, mid - 1, value); }else { return mid; } } }
5.代码实现（非递归方式）
非递归的方法体如下，具体见注释：
/** * * @param array 数组 * @param value 待查找的值 * @return 查找到value则返回索引值；否则返回-1 */ public static int binarySearch(int[] array, int value){ int left = 0; int right = array.length - 1; // 只要left <= right 就一直查找 while (left <= right){ int mid = (left + right) / 2; // mid放在循环内声明是因为mid也需要更新 if(value > array[mid]){ // 向右查找,更新left = mid + 1 left = mid + 1; }else if(value < array[mid]){ // 向左查找,更新right = mid - 1 right = mid - 1; }else { return mid; } } // 出了循环说明没有找到,就返回-1 return -1; }
6.运行结果
设待查找值设置为99 、 0，在array[N] = [1,10,20,30,99,1020]中查找。运行结果如下（99在数组内，故返回索引4；0不在数组中，故返回-1）
7.代码优化（针对线性表中有重复关键字的情况）
这一部分，我们以递归方式实现的代码优化为例，思路如下：
取示例array[N] = {1,10,20,30,99, 99, 99, 1020}，我们需要查找99
先找到mid，但是不要直接返回mid
以mid为起点向左侧扫描，将所有关键字为99的下标记录到ArrayList集合
再次以mid为起点向右侧扫描，将所有关键字为99的下标记录到ArrayList集合
注意mid只用记录一次
返回ArrayList，遍历ArrayList即可得到所有索引
优化代码如下：
import java.util.ArrayList; public class BinarySearch { public static void main(String[] args) { int[] array = {1,10,20,30,99, 99, 99, 1020}; // 待查找值设置为99 、 0 int value1 = 99; int value2 = 0; System.out.println(value1 + "'s index: " + bs(array,0,array.length-1,value1)); System.out.println(value2 + "'s index: " + bs(array,0,array.length-1,value2)); } // 二分查找递归实现 /** * * @param array 数组 * @param left 左端点 * @param right 右端点 * @param value 待查找的值 * @return 查找到value则返回索引值；否则返回空集合 */ public static ArrayList<Integer> bs(int[] array, int left, int right, int value) { // 没有找到 if(left > right){ return new ArrayList(); } int mid = (left + right) / 2; if(value > array[mid]){ // 向右查找,更新left = mid + 1 return bs(array, mid + 1, right, value); }else if(value < array[mid]){ // 向左查找,更新right = mid - 1 return bs(array, left, mid - 1, value); }else { ArrayList<Integer> res = new ArrayList<>(); // 扫描左侧 int index = mid - 1; while (true){ if(index < 0 || array[index] != value){ break; } res.add(index); index--; } // mid记录一次 res.add(mid); // 扫描右侧 index = mid + 1; while (true){ if(index > array.length - 1 || array[index] != value){ break; } res.add(index); index++; } return res; } } }
8.运行结果（优化后）
取示例array[N] = {1,10,20,30,99, 99, 99, 1020}，我们查找99、0，应该返回4、5、6和空。
