알고리즘) Linear/Binary Search (선형/이진 검색)

Sequential/Linear Search (순차/선형 검색)

가장 기본적인 처음부터 끝까지 차례대로 방문하며 찾는 것.
당연히 구현은 쉬우나 자료가 많을수록 비효율적이다.

1. 정렬되지않은 자료

   • 처음부터 끝까지 방문
   • 평균 시간복잡도 O(n)

2. 정렬된 자료

   • 찾는 값보다 큰값을 만나면 검색 종료
   • 평균 비교횟수는 절반으로 줄어드나, 여전히 평균 시간복잡도 O(n)

간단하므로 코드 생략

Binary Search (이진 검색)

자료의 가운데값을 기준으로, 찾는값이 작으면 왼쪽부분을 크면 오른쪽부분을 대상으로 다시 찾는과정 반복.
검색범위를 반으로 줄여가며 이진검색을 반복.

• 자료가 정렬된 상태에서만 사용가능 => 검색성능은 좋으나, 자료정렬 유지비용 발생
• 시간 복잡도 O(log2n)

import java.lang.Math;
import java.util.Scanner;;

public class Test {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = (int) (Math.random() * 100);
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        // Bubble Sort
        for(int i=n-1; i>=0; i--) {
            for(int k=0; k<i; k++) {
                if(arr[k] > arr[k+1]) {
                    int tmp = arr[k];
                    arr[k] = arr[k+1];
                    arr[k+1] = tmp;
                }
            }
        }

        for(int i=0; i<n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        // Binary Search
        int questionNumber = scanner.nextInt();
        for(int i=0; i<questionNumber; i++) {
            int x = scanner.nextInt();
            int left = 0, right = n-1;
            Boolean exist=false;

            while(left <= right) {
                int mid = (left+right)/2;
                if(x == arr[mid]) {
                    exist = true;
                    break;
                } else if(x < arr[mid])
                    right = mid-1;
                else
                    left = mid+1;
            }

            System.out.println(exist);
        }

    }

}