二分查找

一、时间复杂度

假设数据量是n、则每次查找的数据量分别是n、n/2、n/4、n/8、……n/2^k 。

k就是在找到数据的时候总共缩小的次数、而每次缩小的操作都只涉及两个数的操作、时间时间复杂度就是 n/2^k=1、即只剩一个数据的时候。k=log2n、所以时间复杂度就是O(logN)。

二、使用条件

1、依赖顺序结构-数组

2、给定的数组需要有序

3、数据量过大或者过小都不适合二分查找。

->需要全部将数据加载到连续的内存当中、比如100M的数据、或者1G的数据、都需要对应的连续内存。

三、案例

1、查找指定数组中给定值的第一个值的下标

 1 /**
 2      * 二分查找
 3      * 查找数组中 第一个值为value 的下标 不存在返回-1
 4      * @param arr
 5      * @param len
 6      * @param value
 7      * @return
 8      */
 9     public static int binarySearch(int [] arr, int len,int value){
10         int low =0;
11         int high=len-1;
12         while(low<=high){
13             int mid=low+((high-low)>>1);
14             int temp=arr[mid];
15             if(temp>value){
16                high=mid-1;
17             }else if(temp<value){
18                 low =mid+1;
19             }else{
20                 if(mid==0 || arr[mid-1]!=value){//索引为第一个 则肯定是
21                     return mid;
22                 }else{//如果找到的索引的前一个仍然是的话、则需要调整最高索引的值
23                     high=mid-1;
24                 }
25             }
26 
27         }
28         return -1;
29     }

2、其他变种案例

a、查找最后一个等于给定值

b、查找第一个大于等于给定值

c、查找最后一个小于等于给定值