当前位置：首页 -> AI编程基础 -> linux编程基础

随机生成指定顺序序列与二分查找(二)

2014-11-23 19:15:50 · 作者: · 浏览: 77
标签: 随机 生成 指定 顺序 序列 二分 查找
hashSet.add((int) (Math.random() * (high - low) + low));
// lose low value if cotains negative
hashSet.add((int) (Math.random() * (high - low)) + low);
}
// 转化为数组
Object[] temp = hashSet.toArray();
// 用集合的比较器Comparator实现定制排序
if ("desc".equalsIgnoreCase(sort_detatile)) {
Arrays.sort(temp, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// TODO Auto-generated method stub
return (Integer) o2 - (Integer) o1;
}
});
} else if ("asc".equalsIgnoreCase(sort_detatile)
|| "".equals(sort_detatile) || sort_detatile == null) {
Arrays.sort(temp);// default asc
} else {
System.out.println("error sort details");
return null;
}
// 将排序后的数组转化为list输出
List list = new ArrayList(size);
for (Object object : temp) {
list.add((Integer) object);
}
// 销毁temp的引用
temp = null;
return list;
}
/**
*


* MethodName: find_By_BinarySearch

* Description: 調用查找方法

* Create_By: Wangxin

* Create_Date: 2014年8月24日 下午4:00:06

* Modification with annotation or not

*


*
* @param list
* @return int

*/
private static int find_By_BinarySearch(List list, int key,
Integer low, Integer high) {
log = new ArrayList(0);
// if (low == null) {
// low = 0;
// }
// if (high == null) {
// high = list.size();
// }
if (list.size() >= 2 && list.get(0) > list.get(1)) {
return binarySearch_DESC(list, key, low, high);
} else {
return binarySearch(list, key, low, high);
}
}
/**
*
*


* MethodName: binarySearch

* Description: 二分法之正序list查找

* Create_By: Wangxin

* Create_Date: 2014年8月24日 下午4:37:22

* Modification with annotation or not

*


*
* @param list
* @param key
* @param low
* @param high
* @return int

*/
private static int binarySearch(List list, int key, int low,
int high) {
if (low > high)
return -1;
int mid = (low + high) / 2;
log.add(list.get(mid));
if (list.get(mid) == key) {
return mid;
} else if (list.get(mid) < key) {
return binarySearch(list, key, mid + 1, high);
} else {
return binarySearch(list, key, low, mid - 1);
}
}
/**
*
*


* MethodName: binarySearch_DESC

* Description: 二分法之逆序list查找

* Create_By: Wangxin

* Create_Date: 2014年8月24日 下午6:18:16

* Modification with annotation or not

*


*
* @param list
* @param key
* @param low
* @param high
* @return int

*/
private static int binarySearch_DESC(List list, int key, int low,
int high) {
if (low > high)
return -1;
int mid = (low + high) / 2;
log.add(list.get(mid));
if (list.get(mid) == key) {
return mid;
} else if (list.get(mid) < key) {
return binarySearch_DESC(list, key, low, mid - 1);
} else {
return binarySearch_DESC(list, key, mid + 1, high);
}
}
}


output:


[0, 4, 7, 8, 17, 22, 23, 27, 50, 62]


不存在 元素 10


查找次数：4


顺序: 0-->4-->7-->17


[19, 18, 17, 16, 15, 14, 10, 9, 4, 2]


不存在 元素 7


查找次数：3


顺序: 19-->18-->16