我正在尝试编写一个程序,该程序在一个名为的数组中进行顺序搜索和二进制搜索,该数组items
具有 10000 个排序的随机int
值。调用的第二个数组targets
加载了 1000 个int
值(来自items
数组的 500 个值和不在数组中的 500 个值items
)。
基本上,搜索需要通过 items 数组来查找数组中的int
值targets
。这是我的代码:
import java.util.*;
// Loads two arrays with integers
// Searches the arrays using sequential search and binary search
// Compares the time for each search
public class Searches {
private int items[], targets[];
public Searches() {
this.items = new int[10000];
this.targets = new int[1000];
}
public void loadItemsAndTargets(){
int nextValue = 100;
int index = 0;
Random generator = new Random(1);
items[0] = nextValue;
/* load the items array with items to be searched through */
for (index = 1; index < items.length; index++){
nextValue = nextValue + generator.nextInt(100);
items[index]= nextValue;
}
/* load the targets array with target values that will be searched for within
* array items, and target values that are not within array items
*/
index = 0;
while (index < targets.length){
targets[index] = items[index*10];
targets[index+1] = generator.nextInt(100);
index = index + 2;
}
}
public int sequentialSearch(int target) {
/* Using the sequential search algorithm, search the items array for the target value passed
* If found, return the index in the items array, otherwise return -1
*/
this.loadItemsAndTargets();
int key = target;
int index;
boolean found = false;
index = 0;
while ((!found) && (index < items.length))
if (key == target)
found = true;
else
index = index + 1;
if (!found)
index = -1;
return index;
}
public int binarySearch(int target){
/* Using the binary search algorithm, search the items array for the target value passed
* If found, return the index in the items array, otherwise return -1
*/
this.loadItemsAndTargets();
target = targets.length;
int key = target;
boolean found = false;
int guess = 0;
int low = 0;
int high = items.length - 1;
while ((!found) && (low < high)) {
guess = (high+low)/2;
if (key == items[guess])
found = true;
else if (key < items[guess])
high = guess - 1;
else
low = guess + 1;
if (!found)
return - 1;
}
return guess;
}
public static void main(String[] args) {
int index = 0;
Searches searcher = new Searches();
searcher.loadItemsAndTargets();
/* call the method that searches array items
* for each of the values in array targets
* using the sequential search algorithm
* print the approximate elapsed time in milliseconds
* For the FIRST FIVE searches print out the index
* where target value was found or print -1 if it was not found
*/
long startTimeSequential;
startTimeSequential = System.currentTimeMillis();
System.out.println(searcher.sequentialSearch(index));
long endTimeSequential;
endTimeSequential = System.currentTimeMillis();
long totalTimeSequential;
totalTimeSequential = endTimeSequential-startTimeSequential;
System.out.println("sequential search time: " + totalTimeSequential + " milliseconds");
/* call the method that searches array items
* for each of the values in array targets
* using the binary search algorithm
* print the approximate elapsed time in milliseconds
* For the FIRST FIVE searches print out the index
* where target value was found or print -1 if it was not found
*/
long startTimeBinary;
startTimeBinary = System.currentTimeMillis();
System.out.println(searcher.binarySearch(index));
long endTimeBinary;
endTimeBinary = System.currentTimeMillis();
long totalTimeBinary;
totalTimeBinary = endTimeBinary - startTimeBinary;
System.out.println("binary search time: " + totalTimeBinary + " milliseconds");
}
}
编辑:输出应该是这个>
395
986
-1
14
-1
顺序搜索时间:40 毫秒
395
986
-1
14
-1
二分查找时间:0毫秒