随机生成指定顺序序列与二分查找
1.随机生成 K 个整数；☆
2.随机生成 K 个不重复的整数；☆☆
3.随机生成 K 个不重复且有序的整数；☆☆
4.查找 3 中是否存在某个数，若存在给出索引位置；☆☆☆
5.随机生成 K 个不重复且降序排列的整数；★
6.随机生成 K 个不重复且降序排列的在一定范围[M-N]内的整数；★☆
7.随机生成 K 个不重复且降序和升序排列的在一定范围[M-N]内的整数，并查找某个数是否存在其中，存在给出位置，不存在给出提示；★★☆
用Python实现二分查找
根据 7 所述，输出示例如下：
[10, 14, 17, 46, 48, 59, 60, 79, 85, 86]
存在 元素 10 索引为： 0
查找次数：3
顺序: 10-->14-->46
[17, 16, 15, 13, 11, 10, 9, 7, 2, 0]
存在 元素 7 索引为： 7
查找次数：2
顺序: 17-->15
这里给出 7 的源码
/**
* Project Interview
* Package com.java.interview.algorithm.sort
* FileName QuickBinarySearch.java
* Description TODO
* CompanyITSer LTD.
* Copyright 2014
* All rights Reserved, Designed By ITSer
*
* @author Dev-Wangxin
* @version V1.0
* Createdate 2014年8月24日 下午2:09:59
*
* Modification History
* Date Author Version Description
* -----------------------------------------------------------------------------------
* 2014年8月24日 Wangxin 1.0 1.0
* Why & What is modified
*/
package com.java.interview.algorithm.sort;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
*
* ClassName QuickBinarySearch<BR>
* Description TODO<BR>
*
* @author Dev-Wangxin
* @date 2014年8月24日 下午3:53:45
*
*/
public class QuickBinarySearch {
// Recording the process
private static ArrayList<Integer> log;
/**
*
* <p>
* MethodName: main<BR>
* Description: TODO<BR>
* Create_By: Wangxin<BR>
* Create_Date: 2014年8月24日 下午3:53:45<BR>
* Modification with annotation or not<BR>
* </p>
*
* @author Wangxin
* @param args
* @return void<BR>
*/
public static void main(String[] args) {
// create_Array(1, 9, 4, "desc");
// create_Array(-3, 6, 4, "asc");
// create_Array(-3, 6, 4, "");
// create_Array(-3, 6, 4, null);
Integer k1 = 10;
Integer k2 = 8;
List<Integer> l1 = create_Array(0, 100, k1, null);
List<Integer> l2 = create_Array(0, 20, k1, "desc");
position(l1, 10, 0, k1);
position(l2, 7, null, null);
}
/**
* <p>
* MethodName: position<BR>
* Description: 输出key所在位置和查找顺序<BR>
* Create_By: Wangxin<BR>
* Create_Date: 2014年8月24日 下午4:15:16<BR>
* Modification with annotation or not<BR>
* </p>
*
* @param create_Array
* @param i
* @return void<BR>
*/
private static void position(List<Integer> list, int key, Integer start,
Integer end) {
if (start == null) {
start = 0;
}
if (end == null) {
end = list.size() - 1;
}
if (start > end || end > list.size() || start < 0) {
System.out.println("Error Paramerers!");
System.exit(0);
}
int pos = find_By_BinarySearch(list, key, start, end);
if (pos != -1) {
System.out.println("\n" + list + " \n 存在 元素 " + key + " 索引为： "
+ pos);
System.out.print("查找次数：" + log.size() + "\n顺序: ");
for (int i = 0; i < log.size() - 1; i++) {
System.out.print(list.get(i) + "-->");
}
System.out.println(list.get(log.size()));
} else {
System.out.println("\n" + list + " \n 不存在 元素 " + key);
System.out.print("查找次数：" + log.size() + "\n顺序: ");
for (int i = 0; i < log.size() - 1; i++) {
System.out.print(list.get(i) + "-->");
}
System.out.println(list.get(log.size()));
}
}
/**
*
* <p>
* MethodName: create_Array<BR>
* Description: 创建有序数组或list，逆序或正序<BR>
* Create_By: Wangxin<BR>
* Create_Date: 2014年8月24日 下午4:20:24<BR>
* Modification with annotation or not<BR>
* </p>
*
* @param low
* 下区间
* @param high
* 上区间
* @param size
* 生成数的个数
* @param sort_detatile
* 升降序描述
* @return List<Integer><BR>
*/
private static List<Integer> create_Array(int low, int high, int size,
String sort_detatile) {
// size 为 0 ，或区间不满足要求，则终止运行
if (size <= 0 || (high - low) < size) {
System.out.println("error input!");
return null;
}
Set<Integer> hashSet = new HashSet<Integer>(size);
// 用 set 去重
while (hashSet.size() < size) {
// (int) Math.random() * (high - low + 1) == 0
// 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<Object>() {
@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<Integer> list = new ArrayList<Integer>(size);
for (Object object : temp) {
list.add((Integer) object);
}
// 销毁temp的引用
temp = null;
return list;
}
/**
* <p>
* MethodName: find_By_BinarySearch<BR>
* Description: 調用查找方法<BR>
* Create_By: Wangxin<BR>
* Create_Date: 2014年8月24日 下午4:00:06<BR>
* Modification with annotation or not<BR>
* </p>
*
* @param list
* @return int<BR>
*/
private static int find_By_BinarySearch(List<Integer> list, int key,
Integer low, Integer high) {
log = new ArrayList<Integer>(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);
}
}
/**
*
* <p>
* MethodName: binarySearch<BR>
* Description: 二分法之正序list查找<BR>
* Create_By: Wangxin<BR>
* Create_Date: 2014年8月24日 下午4:37:22<BR>
* Modification with annotation or not<BR>
* </p>
*
* @param list
* @param key
* @param low
* @param high
* @return int<BR>
*/
private static int binarySearch(List<Integer> 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);
}
}
/**
*
* <p>
* MethodName: binarySearch_DESC<BR>
* Description: 二分法之逆序list查找<BR>
* Create_By: Wangxin<BR>
* Create_Date: 2014年8月24日 下午6:18:16<BR>
* Modification with annotation or not<BR>
* </p>
*
* @param list
* @param key
* @param low
* @param high
* @return int<BR>
*/
private static int binarySearch_DESC(List<Integer> 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]