歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

隨機生成指定順序序列與二分查找

隨機生成指定順序序列與二分查找

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

 

Copyright © Linux教程網 All Rights Reserved