二分搜索算法详解（Binary Search）

二分搜索（Binary Search）

• 如何确定一个元素在数组中的位置？（假设数组里面全都是整数）
• 如果是无序数组，从第0个位置开始遍历搜索，平均时间复杂度：O(n)
• 如果是有序数组，可以使用二分搜索，最坏时间复杂度为O(logn)

（一）、二分搜索 — 思路

• 假设在[begin，end）范围内搜索某个元素 v，mid == （begin + end）/ 2 ①、如果v< m，去[begin ， mid）范围内二分搜索 ②、如果v> m，去[mid + 1， end）范围内二分搜索 ③、如果v == m ，直接返回 mid
• end指的是数组的长度。

（二）、二分搜索 — 实例

（三）、二分搜索 — 实现

importorg.junit.Test;importjava.util.Arrays;/**
* 查找v在有序数组array中的位置
*/publicclassBinarySearch{publicintindexOf(int[] array,int v){if(array ==null|| array.length ==0)return-1;int begin =0;int end = array.length;while(begin < end){int mid =(begin + end)>>1;if(v < array[mid]){
                end = mid;}elseif(v > array[mid]){
                begin = mid+1;}else{return mid;}}return-1;}@Testpublicvoidtest(){int[] array ={2,4,8,8,9,13,10};System.out.println(Arrays.toString(array));System.out.println(indexOf(array,8));}}
运行结果：
[2,4,6,8,9,13,10]3

• 思考？？？ 如果存在多个重复的值，返回的是哪一个？
• 例如：[2，4， 8， 8， 9， 13， 10] 我们通过运行上述的代码，可以看到，它的返回值是3，而不是2，因此我们可以得出结论如果存在多个重复的值，返回的值不确定。

（四）、二分搜索优化

• 在元素 v 的插入过程中，可以先用二分搜索出合适的插入位置，然后再将元素v插入。
• 要求二分搜索返回的插入位置：第1个大于 v 的元素位置 ①、如果 v 是 5，返回 2 ②、如果 v 是 1，返回 0 ③、如果 v 是 15，返回 7 ④、如果 v 是 8，返回 5

（1）、二分搜索优化 — 思路

• 假设在[begin，end）范围内搜索某个元素 v，mid == （begin + end）/ 2 ①、如果v< m，去[begin ， mid）范围内二分搜索 ②、如果v>= m，去[mid + 1， end）范围内二分搜索
• end指的是数组的长度。

（2）、 二分搜索优化 — 实例

importorg.junit.Test;importjava.util.Arrays;publicclassBinarySearch{/**
     * 查找v在有序数组array中待插入位置
     */publicstaticintsearch(int[] array,int v){if(array ==null|| array.length ==0)return-1;int begin =0;int end = array.length;while(begin < end){int mid =(begin + end)>>1;if(v < array[mid]){
                end = mid;}else{
                begin = mid+1;}}return begin;}@Testpublicvoidtest2(){int[] array ={2,4,8,8,8,12,14};System.out.println(Arrays.toString(array));System.out.println(search(array,5)==2);System.out.println(search(array,1)==0);System.out.println(search(array,15)==7);System.out.println(search(array,8)==5);}}
运行结果：
[2,4,8,8,8,12,14]truetruetruetrue