爪哇 - 比較線性搜索和二分搜索的性能

可能重複：
What is the difference between Linear search and Binary search?爪哇 - 比較線性搜索和二分搜索的性能

收件從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)"); 
    } 
}

我可以得到線性搜索的環數。但是，我無法獲得二進制搜索循環數。

來源

2012-10-21 user1761325

你是什麼意思，你「無法得到它」？你有什麼錯誤嗎？ – alestanis

「比較線性搜索和二進制搜索的性能」可能也意味着執行比較的次數，而不是計算循環次數。 – Sujay

System.out.println（「Binary search - 」+ loop2 +「loop（s）」）的輸出是什麼;'？ – mcalex

我建議使用比較計數來代替循環計數，因爲它反映了更多算法的成本。您可以輕鬆計數比較。但在這個特殊情況下，兩者恰好相同。

int comparisons = 0; 
while (low <= high) { 
    middle = (low + high)/2; 
    ++comparisons; 
    if (num2 > num[ middle ]) { 
     low = middle +1; 
    } 
    else if (num2 < num[ middle ]) { 
     high = middle - 1; 
    } 
    else { 
     break; 
    }    
} 
System.out.println("Binary search - " + comprisons + " loop(s)");

來源

2012-10-21 10:18:01 Aubin

Downvoting。如果要計算比較次數，則應計算if語句的兩個分支。數一半是不夠的。即使是平等的情況也是一個比較。所以，循環計數是正確的。 – rrufai

你說得對，對不起。我編輯了源代碼。 – Aubin

謝謝，這是非常有用的 – user1761325

您的二進制搜索缺少磨合：

 if (num2 == num[ middle ]) { 

     }

而且您的二進制搜索是按升序排列，但你實際上有一個遞減順序！反轉您的排序或調整您的搜索算法。

來源

2012-10-21 10:44:15 Eelke

爪哇 - 比較線性搜索和二分搜索的性能

回答

相關問題