前言
最进在学习过程遇到二分查找，有所收获，特作如下整理，如有不妥，请指正！
介绍
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
特点
时间复杂度
最好情况：O(1)
平均情况: O（ log 2 n ）
最坏情况: O（ log 2 n ）
空间复杂度：O(1)
稳定性：稳定
使用条件
必须采用顺序存储结构
必须按关键字大小有序排列
基本思想
二分查找是一种非常高效的算法，又称之为折半查找，顾名思义就是将查找的值和数组的中间值作比较
如果被查找的值小于中间值，就在中间值左侧数组继续查找；如果大于中间值，就在中间值右侧数组中查找；否则中间值就是要找的元素。
二分查找的优缺点：
优点：比较次数少，查找速度快，平均性能好；
缺点：要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
实现
假设存在这样一个数组a[8]，数组中存在有8个按顺序存储的数：
a[8] = [1,2,3,4,5,6,7,8];
用表格来将这个数组展示出来，表格如下：
表格①
首先，取数组的初始索引值（low=0），末尾索引值（high=7），再根据这两个值取中间索引值（mid = （low + high） / 2 = 3），将这三个表示加入到表格中，表格如下：
表格②
假设这里想要查找的值是“5”。
这时比较5与mid索引的值（4），因为5>4，所以需要查找以mid为分界线的右半区。此时，low的索引值变为low = mid + 1 = 4，而mid的值转变为mid = （low + high） / 2 = 5，表格如下：
表格③
这时比较5与mid索引的值（6），因为5<6，所以需要查找以mid为分界线的左半区。此时，high的索引值变为high = mid - 1 = 4，而mid的值转变为mid = （low + high） / 2 = 4，表格如下：
表格④
此时，mid的索引对应的值与想要查找的值对应，查找结束。
总结
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
思路分析：
1.首先确定该数组的中间下标mid=（left+right）/2
2.然后让需要查找的数value和arr[mid]比较
2.1 value>arr[mid]，说明查找的数在mid的右边，因此需要递归向右查找
2.2 value
2.3 value=arr[mid]，说明找到，就返回
//什么时候需要结束递归
1）找到就结束递归
2）递归完整个数组，仍然没有找到value，也需要结束递归，当left>right就需要退出
代码实现
public static int binarySearch(Integer[] srcArray, int value) { //定义初始最小、最大索引 int start = 0; int end = srcArray.length - 1; //确保不会出现重复查找，越界 while (start <= end) { //计算出中间索引值 int middle = (end + start)>>>1 ;//防止溢出 if (value == srcArray[middle]) { return middle; //判断下限 } else if (value < srcArray[middle]) { end = middle - 1; //判断上限 } else { start = middle + 1; } } //若没有，则返回-1 return -1; }
参考：Java实现二分法查找数组
package cn.kgc.kb03.sort; import java.util.ArrayList; import java.util.List; /** * @author：BeiisBei * @date：2019/9/8 * @aim：二分查找 */ public class BinarySearch { public static void main(String[] args) { int arr[]={1,34,56,200,200,200,1000,1999}; // int resIndex = binarySearch(arr,0,arr.length-1,1); // System.out.println("resIndex"+"="+resIndex); List<Integer> resIndexList=binarySearch2(arr,0,arr.length-1,200); System.out.println("resIndexList ="+resIndexList); } //二分查找算法 /** * * @param arr 数组 * @param left 左边的索引 * @param right 右边的索引 * @param findValue 要查找的值 * @return 如果找到就返回下标，如果没有找到，就返回-1 */ public static List<Integer> binarySearch2(int[] arr, int left, int right, int findValue) { //当left>right 时，说明递归整个数组，还是没有找到 if(left>right){ return new ArrayList<Integer>(); } int mid = (left+right)/2; int midValue = arr[mid]; if(findValue>midValue){ //向右递归 return binarySearch2(arr,mid+1,right,findValue); } else if(findValue<midValue){ //向左递归 return binarySearch2(arr,left,mid-1,findValue); } else{ // 1. 在找到mid索引值，不要马上返回 // 2. 向mid 索引值的左边扫描，将所有满足200的元素下标，加入到集合ArrayList // 3. 向mid 索引值的右边扫描，将所有满足200的元素下标，加入到集合ArrayList // 4. 将ArrayList返回 List<Integer> resIndexlist = new ArrayList<Integer>(); //向mid 索引值的左边扫描，将所有满足200的元素下标，加入到集合ArrayList int temp=mid - 1; while(true){ if(temp<0 || arr[temp]!= findValue){ //退出 break; } //否则temp 放入到resIndexlist resIndexlist.add(temp); temp -= 1; //temp 左移 } resIndexlist.add(mid); //向mid 索引值的右边扫描，将所有满足200的元素下标，加入到集合ArrayList temp=mid + 1; while(true){ if(temp>arr.length-1 || arr[temp]!= findValue){ //退出 break; } //否则temp 放入到resIndexlist resIndexlist.add(temp); temp += 1; //temp 右移 } return resIndexlist; } } /**当一个有序数组种，有多个相同数值时，如何将所有的数值查找到 * 比如数组中的200 * * 思路分析： * 1. 在找到mid索引值，不要马上返回 * 2. 向mid 索引值的左边扫描，将所有满足200的元素下标，加入到集合ArrayList * 3. 向mid 索引值的右边扫描，将所有满足200的元素下标，加入到集合ArrayList * 4. 将ArrayList返回 */ }
