隨機生成指定順序序列與二分查找
1.隨機生成 K 個整數；☆
2.隨機生成 K 個不重復的整數；☆☆
3.隨機生成 K 個不重復且有序的整數；☆☆
4.查找 3 中是否存在某個數，若存在給出索引位置；☆☆☆
5.隨機生成 K 個不重復且降序排列的整數；★
6.隨機生成 K 個不重復且降序排列的在一定范圍[M-N]內的整數；★☆
7.隨機生成 K 個不重復且降序和升序排列的在一定范圍[M-N]內的整數，並查找某個數是否存在其中，存在給出位置，不存在給出提示；★★☆
Golang二分查找算法的簡單實現 http://www.linuxidc.com/Linux/2014-02/96093.htm
二分查找改進版 http://www.linuxidc.com/Linux/2013-10/91721.htm
二分查找的實現及注意事項 http://www.linuxidc.com/Linux/2013-07/87308.htm
用Python實現二分查找 http://www.linuxidc.com/Linux/2012-12/75948.htm
二分查找之Java實現 http://www.linuxidc.com/Linux/2012-05/59869.htm
Java針對數組的普通查找法和二分查找法 http://www.linuxidc.com/Linux/2012-03/57065.htm
根據 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]
不存在 元素 7
查找次數：3
順序: 19-->18-->16
