package org.nxt.algorithm.search;
/**
* the bean of comparable
* @author nanxiaotao
*
*/
public class ComparableBean implements Comparable<ComparableBean> {
private int value;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
@Override
public int compareTo(ComparableBean o) {
if(this.value<o.getValue()) {
return -1;
}else if(this.value==o.getValue()) {
return 0;
}else {
return 1;
}
}
}
1.线性查找
适用场景：顺序存储或链接存储的线性表
时间复杂度:O(n)
package org.nxt.algorithm.search;
/**
* linear search
* @author nanxiaotao
*
*/
public class LinearSearch {
/**
* search
* @param datas aggregate of the data
* @param target the object to look for
* @return
*/
public static ComparableBean search(ComparableBean [] datas,ComparableBean target) {
ComparableBean result=null;//Object found
for(int i=0;i<datas.length;i++) {
//Traverse the collection
ComparableBean item=datas[i];//get the element of a collection by index
//compare the current element to the target object
if(0==item.compareTo(target)) {
//if they are equal,assign and break out of the loop
result=item;
break;
}
}
return result;
}
}
1.二分查找
适用场景：已经有序
时间复杂度:O(log2n)
package org.nxt.algorithm.search;
/**
* Binary Search
* @author nanxiaotao
*
*/
public class BinarySearch {
/**
* search
* @param datas datas aggregate of the data
* @param target target the object to look for
*/
public static ComparableBean search(ComparableBean [] datas,ComparableBean target) {
ComparableBean result=null;//Object found
int first=0;//the first index of collection
int last=datas.length-1;//the last index of collection
int mid;//the middle index of colleciton
/**
* Traverse the collection
* suspensive condition:
* 1:find the target
* 2:the first index equals the last index
*/
while(result==null&&first<=last) {
mid=(first+last)/2;//compute the middle index
if(datas[mid].compareTo(target)==0) {
//equal
result=datas[mid];
}else {
if(datas[mid].compareTo(target)==-1) {
//smaller
first=first+1;
}else {
//bigger
last=last-1;
}
}
}
return result;
}
}
