可能重复:线性搜索和二进制搜索有什么区别?
编写一个程序,在0到100的范围内生成20个随机整数 . 按降序对数组进行排序 . 然后,接受来自用户的整数输入 . 然后,使用此编号搜索阵列 . 比较线性搜索和二分查找的性能 .
这是我的代码
import java.util.Arrays;
import java.util.Scanner;
public class search {
public static void main(String args[]) {
int[] num = new int[20];
for (int i = 0; i < num.length; i++) {
num[i] = (int) (Math.random() * 101);
}
System.out.println("A list of 20 random intergers with 0 - 100");
System.out.println(Arrays.toString(num));
for (int j = 1; j < num.length; j++) {
for (int k = 0; k < num.length - 1; k++) {
if (num[k] < num[k + 1]) {
int hold = num[k + 1];
num[k + 1] = num[k];
num[k] = hold;
}
}
}
System.out.println("Array in descending order");
System.out.println(Arrays.toString(num));
Scanner input = new Scanner(System.in);
System.out.print("Enter a number to search: ");
int num2 = input.nextInt();
int loop = 0;
for ( int cnt = 0; cnt < num.length; cnt++ )
{
if ( num[cnt] == num2 )
{
loop = cnt;
System.out.println(num2+ " found");
}
}
System.out.println("Linear search - "+loop+ " loop(s)");
int loop2 = 0;
int low = 0; // low element subscript
int high = num.length - 1; // high element subscript
int middle; // middle element subscript
while ( low <= high ) {
middle = ( low + high ) / 2;
if ( num2 == num[ middle ] ) {
}
else if ( num2 > num[ middle ] )
{
low = middle +1;
loop2++;
}
else{
high = middle - 1;
loop2++;
}
}
System.out.println("Binary search - "+loop2+ " loop(s)");
}
}
我可以获得线性搜索的循环次数 . 但是,我无法获得二进制搜索循环数 .
2 回答
我建议使用比较计数代替循环计数,因为它反映了更多的算法成本 . 您可以轻松计算比较 . 但在这种特殊情况下,两者恰好相同 .
您的二进制搜索缺少中断:
您的二进制搜索也是升序,但实际上您有降序!要么反转排序,要么调整搜索算法 .