二分搜索是一种非常高效的搜索算法。 也称为折半检索。
最初在用数据结构学习递归时实现了二分搜索，但实际上不用递归也可以实现。 毕竟递归需要打开额外的空间来辅助查询。 本文介绍两种方法
二分搜索算法思想
将有序数组与每次按数组中间位置的数量搜索的关键字进行比较，将搜索范围缩小一半直到匹配成功。
一种方案：将表中央记录的关键词与检索关键词进行比较，两者相等时检索成功； 否则，使用中间位置记录将表分为前、后两个子表。 如果中间位置记录的关键字大于搜索关键字，则进一步搜索前面的子表。 否则，进一步搜索以下子表： 重复上述过程，直到找到满足条件的记录，并且搜索成功或子表不存在。 此时搜索不会成功。
二分搜索图标说明
图为百度图片，感谢分享者
把优缺点分成两部分
具有比较次数少、检索速度快、平均性能好的优点；
缺点是核对表规则，插入删除困难。
因此，混叠搜索方法适于在不频繁改变的情况下搜索频繁有序列表。
使用条件：搜索顺序为顺序结构，有序。
JVA代码实现递归实现/** *使用递归的二分查找* title : recursionbinarysearch * @ param arr规则数组*@param key查找对象关键字*@return查找位置*/publicstaticintrecursionbinarysearch (int [ ] arr、int key、int low、int high ) {if ) keyarr [ low ]|||keyarr [ high () //初始中间位置if(ARR[middle]key ) /如果大于关键字，则关键字为左区域returnrecursionbinarysearch (arr，key，low，middle - 1 )； }elseif(arr[middle]key ) /小于关键字时关键字为右区域returnrecursionbinarysearch (arr，key，middle 1，high )； }else {return middle； }
不使用递归实现(while循环) ) ) ) )。
/** *不使用递归二分查找* title : commonbinarysearch * @ param arr * @ param key * @ return关键字位置*/publicstaticintcommmonbinaryses int middle=0； //middle if (keyarr [ low ]|keyarr [ high ] ) {return -1； }while(low=high ) middle ) (lowhigh )/2； 如果if(arr[middle]key )//大于关键字，则关键字在左区域high=middle - 1； }elseif(arr[middle]key ) /如果小于关键字，则关键字在右区域low=middle 1； }else{return middle； } }返回- 1； //如果最后还没有找到，返回-1}
测试
测试代码：
publicstaticvoidmain (string [ ] args ) int [ ] arr={ 1、3、5、7、9、11 }； int key=4； //int position=recursionbinarysearch (arr，key，0，arr.length - 1 )； int position=commonbinarysearch (arr，key )； if (位置==-1 ) {System.out.println正在查找' key '。 序列中没有这个数！ ' )； (else ) system.out.println ) )为" key "，找到的位置为" position
recursionBinarySearch ()测试： key分别是0、9、10和15的搜索结果
我在找0。 序列中没有这个数。 找9，找位置：找4找10，序列中没有那个数！ 我在找15。 序列中没有这个数。
commonBinarySearch ()测试： key分别为-1、5、6和20的搜索结果
我在找-1。 序列中没有这个数。 要找的是5，找到的位置是2，要找的是6，序列中没有那个数！ 我在找20。 序列中没有这个数。
时间的复杂性采用了分布式策略
最坏情况下，两种方式的时间复杂度相同： o(log2n )。
优选情况下为o(1)
空间复杂度算法的空间复杂度不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数
非递归方式：
辅助空间为常数级，因此如下所示。
空间复杂度为o(1；
递归方法：
递归的次数和深度都为log2 N，每次所需的辅助空间为常数级：
空间复杂性： o(log2n ) ) ) )。