二分查找是一种查询效率非常高的查找算法。又称折半查找。

一、算法思想

有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。

一个情景：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

二、举例图示

要查找的数为21。

第一次将头指针和尾指针分别放置头尾，middle放在中间。将21与中间的56进行比较。21<56，应在左边。

第二次将尾指针放在56得到前一位，middle放在中间。将21与中间的19进行比较。21>19，应在右边。

第三次将头指针放在19的后一位，middle放在中间。将21与21比较，符合查找成功！

三、二分查找优缺点及使用条件

优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

使用条件：查找序列是顺序结构，有序。

四、算法实现

1 packagerecursion;2

3 /**

4 *@authorzsh5 * @company wlgzs6 * @create 2019-02-16 10:117 * @Describe 二分查找的两种实现8 */

9 public classBinarySearch {10

11 /**

12 * 循环实现二分查找13 *@paramarr 待查找的数组14 *@paramkey 待查找的数15 *@returnkey在数组中的索引位置16 */

17 static int binary1(int[] arr,intkey){18 //头指针初始位置

19 int low = 0;20 //尾指针初始位置

21 int high = arr.length -1;22 //定义middle指针位置

23 int middle = 0;24 //头尾交叉 || key大于最大值 || key小于最小值，说明未找到

25 if (low > high || key > arr[high] || key

29 while (low <=high){30 //防止数据溢出

31 middle = (low + high) >>> 1;32 if (arr[middle] >key){33 //middle所对应的值比key大，key应该在左边区域

34 high = middle -1;35 }else if (arr[middle]

37 low = middle +1;38 }else{39 returnmiddle;40 }41

42 }43

44 //最后仍然没有找到，则返回-1

45 return -1;46 }47

48 /**

49 * 递归实现二分查找50 *@paramarr 待查找的数组51 *@paramlow 头指针所在位置52 *@paramhigh 尾指针所在位置53 *@paramkey 待查找的数54 *@returnkey在数组中的索引位置55 * 算法分析：56 * 找重复：57 * 找变化量：58 * 找出口：头尾交叉 || key大于最大值 || key小于最小值59 */

60 static int binary2(int[] arr,int low , int high ,intkey){61

62 //头尾交叉 || key大于最大值 || key小于最小值，说明未找到

63 if (low > high || key > arr[high] || key

67 int middle = (low + high) >>> 1;68

69 //middle所对应的值比key大，key应该在左边区域

70 if (arr[middle] >key){71 binary2(arr,low,middle-1,key);72 }else if (arr[middle]

74 binary2(arr,low+1,high,key);75 }else{76 returnmiddle;77 }78

79 //最后仍然没有找到，则返回-1

80 return -1;81 }82

83 public static voidmain(String[] args) {84 int[] arr = new int[]{5,13,19,21,37,56,64,75,80,88,92};85 System.out.println(binary1(arr,21));86 System.out.println(binary1(arr,21));87 }88

89 }

五、时间复杂度和空间复杂度

时间复杂度：

最坏的情况下两种方式时间复杂度一样：O(log2 N)

最好情况下为O(1)

空间复杂度：算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数

非递归方式：

由于辅助空间是常数级别的所以：空间复杂度是O(1);

递归方式：

递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：空间复杂度：O(log2N )