基本概念

二分查找是一种查询效率非常高的查找算法，又称折半查找。二分查找法是对一组有序的数字中进行查找，传递相应的数据，进行比较查找到与原数据相同的数据，查找到了返回对应的数组下标，没有找到返回-1；

算法基本思想及优缺点

有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。 优点：比较次数少，查找速度快，平均性能好； 缺点：要求待查表为有序表，且插入删除困难。折半查找方法适用于不经常变动而查找频繁的有序列表。

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

应用场景

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

java代码的两种实现方式

1. 递归实现

package dongtaiguihua.demo; //递归的方式实现二分查找的算法 class Sooliytion { //下面这个括号里面的最后两个变量都是表示的是该数组的索引值 public static int recursionBinarySearch(int[] arr,int key, int low, int high){ //这个判断的目的是关键字是否存在于该数组中，同时该数组是否是一个有序数组 if( key < arr[low] || key > arr[high] || low > high ){ return -1; } //计算出中间索引的值，就是数组中间位置的值 int middle =( low + high )/2; //中间索引的值大于我们的关键字，则说明该关键字在中间索引的左边 if(arr[middle] > key){ //使用递归的方式继续执行上述方法, middle-1,是因为之前的中间索引的数值已经进行了比较，接下来执行同样函数的子数组不需要改索引的元素了 return recursionBinarySearch( arr, key, low, middle-1); }else if(arr[middle] < key){ //中间索引的值小于关键字，则关键字位于中间索引的右边 return recursionBinarySearch( arr, key,middle + 1, high); }else{ //中间索引的值与关键字相等的时候返回中间索引 return middle; } } public static void main(String[] args){ int[] arr = {1,3,5,7,9,11}; int key = 9; int position =recursionBinarySearch(arr, key,0,arr.length-1); if( position == -1){ System.out.println("查找的是"+ key + ",序列中没有该数！"); }else{ System.out.println("查找的是" + key + ",找到的位置是"+ position); } } }

2.非递归实现

package dongtaiguihua.demo; //非递归的方法实现二分查找 class Sklojtion { public static int commonBinarySearch(int[] arr,int key){ int low = 0; int high = arr.length-1; int middle = 0; if( key < arr[low] || key > arr[high] || low > high){ return -1; } while( low <= high){ middle =( low + high )/2; if(arr[middle] >key){ high = middle-1; }else if(arr[middle] < key){ low = middle + 1; }else{ return middle; } } return -1; } public static void main(String[] args){ int[] arr = {1,3,5,7,9,11}; int key = 9; int position = commonBinarySearch(arr,key); if( position == -1){ System.out.println("查找的是"+ key + ",序列中没有该数！"); }else{ System.out.println("查找的是" + key + ",找到的位置是"+ position); } } }