随机生成指定顺序序列与二分查找
1.随机生成 K 个整数；☆
2.随机生成 K 个不重复的整数；☆☆
3.随机生成 K 个不重复且有序的整数；☆☆
4.查找 3 中是否存在某个数，若存在给出索引位置；☆☆☆
5.随机生成 K 个不重复且降序排列的整数；★
6.随机生成 K 个不重复且降序排列的在一定范围[M-N]内的整数；★☆
7.随机生成 K 个不重复且降序和升序排列的在一定范围[M-N]内的整数，并查找某个数是否存在其中，存在给出位置，不存在给出提示；★★☆
根据 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
* Description TODO
*
* @author Dev-Wangxin
* @date 2014年8月24日 下午3:53:45
*
*/
public class QuickBinarySearch {
// Recording the process
private static ArrayList log;
/**
*
*
* MethodName: main
* Description: TODO
* Create_By: Wangxin
* Create_Date: 2014年8月24日 下午3:53:45
* Modification with annotation or not
*
*
* @author Wangxin
* @param args
* @return void
*/
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 l1 = create_Array(0, 100, k1, null);
List l2 = create_Array(0, 20, k1, "desc");
position(l1, 10, 0, k1);
position(l2, 7, null, null);
}
/**
*
* MethodName: position
* Description: 输出key所在位置和查找顺序
* Create_By: Wangxin
* Create_Date: 2014年8月24日 下午4:15:16
* Modification with annotation or not
*
*
* @param create_Array
* @param i
* @return void
*/
private static void position(List 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()));
}
}
/**
*
*
* MethodName: create_Array
* Description: 创建有序数组或list，逆序或正序
* Create_By: Wangxin
* Create_Date: 2014年8月24日 下午4:20:24
* Modification with annotation or not
*
*
* @param low
* 下区间
* @param high
* 上区间
* @param size
* 生成数的个数
* @param sort_detatile
* 升降序描述
* @return List
*/
private static List 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 hashSet = new HashSet(size);
// 用 set 去重
while (hashSet.size() < size) {
// (int) Math.random() * (high - low + 1) == 0
//