运行时间中的对数
前一篇文章中分治递归的时间复杂度为O（nlogn）;对数最常出现的规律可概括为如下一般规律：
如果一个算法用常数时间O（1）将问题的大小削减为其的一部分（通常是二分之一），那么该算法就是O（logn）.另一方面，如果一个算法用常数时间O（1）将问题的大小消减一个常数数量（如将问题减少1等等），那么这种sauna就是O（n）的。
折半查找简单引论问题
求x在数组T[]中的坐标，如果不存在x，则返回-1
方案一
思路：直接穷举，进行遍历，时间复杂度O（n），线性增长
代码：
public static <T extends Comparable<? super T>> int binarySearch1(T[] a, T x){ for(int i = 0;i < a.length;i++){ if (a[i].compareTo(x) == 0){//如果相等则直接返回 return i; } } for (T ason:a) { } return -1; }
方案二
思路：折半查找
代码： “` /**
求x在数组T[]中的坐标，如果不存在x，则返回-1
此方法使用折半查找 时间复杂度为O（logn）
@param a
@param x
@param
@return */ public static
>int binarySearch2(T[] a,T x){ int low = 0, high = a.length -1; while (low <= high){
//折半 int mid = (low + high) / 2; //a[mid]更小 查右半部分 if(a[mid].compareTo(x) < 0){ low = mid +1; }else //a[mid]更大 查左边部分 if(a[mid].compareTo(x) > 0){ high = mid -1 ; }else{//a[mid] == x return mid; }} return -1; } “`
完整代码如下：
```
package com.anteoy.coreJava.tmp;
/**
* Created by zhoudazhuang
* Date: 17-3-29
* Time: 下午2:43
* Description : 折半查找算法
*/
public class BinarySearchAlgorithm {
/**
* 求x在数组T[]中的坐标，如果不存在x，则返回-1
* 此方法使用折半查找 时间复杂度为O（logn）
* @param a
* @param x
* @param <T>
* @return
*/
public static <T extends Comparable<? super T>>int binarySearch2(T[] a,T x){
int low = 0, high = a.length -1;
while (low <= high){
//折半
int mid = (low + high) / 2;
//a[mid]更小 查右半部分
if(a[mid].compareTo(x) < 0){
low = mid +1;
}else
//a[mid]更大 查左边部分
if(a[mid].compareTo(x) > 0){
high = mid -1 ;
}else{//a[mid] == x
return mid;
}
}
return -1;
}
public static <T extends Comparable<? super T>> int binarySearch1(T[] a, T x){
for(int i = 0;i < a.length;i++){
if (a[i].compareTo(x) == 0){//如果相等则直接返回
return i;
}
}
for (T ason:a) {
}
return -1;
}
public static void main(String[] args) {
Integer[] array = {1,6,7,8,9,12};
Integer x = 7;
System.out.println(binarySearch1(array,x));
System.out.println(binarySearch2(array,x));
}
}
```
输出：
2 2
参考文献
《数据结构和算法分析第二版》
