자바 - 선형 검색과 이진 검색의 성능을 비교

Question

가능한 중복 :
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)"); 
    } 
} 

내가 선형 검색 루프의 수를 얻을 수있다. 그러나 바이너리 검색 루프 번호를 얻을 수 없습니다.

Answer 1

알고리즘의 비용이 많이 반영되므로 loop-count 대신 compare-count를 사용하는 것이 좋습니다. 당신은 쉽게 비교를 계산할 수 있습니다. 그러나이 특별한 경우에는 두 가지가 동일합니다. 또한 이진 검색은 오름차순입니다

 if (num2 == num[ middle ]) { 

     } 

하지만 당신은 실제로 내림차순이 있습니다

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)"); 

Answer 2

바이너리 검색에 휴식이 없습니다! 정렬을 취소하거나 검색 알고리즘을 조정하십시오.