[JAVA] 순차탐색(Sequential Search), 이진탐색(Binary Search)

---

• 순차탐색 ( Sequential Search )
• 이진탐색 ( Binary Search )

---

int[] arr = {1, 19, 9, 7, 3, 11, 5, 109, 292, 30};

위와 같은 배열이 있을때, 숫자 7이 몇번째에 있는지 알아내고자 한다.

---

순차탐색(Sequential Search)

순차탐색은 말 그대로 차례대로 비교해가면서 찾는것이다.

 

arr[0]부터 하나하나 7인지 아닌지 확인하다 arr[3] 이 7이므로 탐색을 종료하게되는것이다.

 

순차탐색의 복잡도

만약 arr 배열에서 1을 탐색한다면 1번만에 찾아낼것이다.

 

19는 2번만에, 9는 3번만에 찾아낼 것이다.

 

30을 탐색한다면 10번만에 찾아낼것이다.

 

그렇다면, 탐색하는데 걸리는 평균 연산 횟수는 

이 될것이다.

 

따라서 arr 배열의 크기가 n이라면 탐색에 걸리는 평균 연산횟수는 

따라서 복잡도는 O(n)이 된다.

 

예제

public class SequentialSearch {
    public static void main(String args[]) {

        Scanner in = new Scanner(System.in);
        int key = Integer.parseInt(in.nextLine());
        String[] s = in.nextLine().split("\\s+");

        int n = s.length;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = Integer.parseInt(s[i]);
        }
        int result = sequentialSearch(data, key);

        System.out.println(result);

        in.close();
    }

    static int sequentialSearch(int arr[], int x) {
        int n = arr.length;
        int key = x;
        int[] array = arr;
        int rt = 0;
        for(int i = 0; i<n; i++){
            if(array[i]==key){
                rt = i;
                break;
            }
            rt = -1;
        }

        return rt;
    }
}

---

이진탐색(Binary Search)

이진탐색은 탐색할때마다 탐색 범위가 반으로 줄어든다.

 

그리고, 이진탐색을 하기위해서는 배열이 정렬되어있어야한다.

[1회]

정렬된 배열에서 (첫번째 인덱스 + 마지막 인덱스)/2 의 키값과 찾고자 하는 값을 비교한다.

찾고자 하는 값이 더 크므로, (첫번째 인덱스 + 마지막 인덱스)/2 + 1 값이 다음 탐색의 첫번째 인덱스가 된다.

[2회]

(첫번째 인덱스 + 마지막 인덱스)/2 의 키값과 찾고자 하는 값을 비교한다.

찾고자 하는 값이 더 크므로, (첫번째 인덱스 + 마지막 인덱스)/2 + 1 값이 다음 탐색의 첫번째 인덱스가 된다.

[3회]

(첫번째 인덱스 + 마지막 인덱스)/2 의 키값과 찾고자 하는 값을 비교한다.

키값과 찾고자 하는 값이 같으므로, 탐색을 종료한다.

 

이진탐색의 복잡도

탐색하는 배열의 크기가 n이고, k번의 연산을 통해 원하는 값을 찾았다고 가정한다.

 

한번 연산을 하면 탐색해야 할 n개의 숫자가 반으로 줄어든다. 즉,

두번 연산을 하면 탐색해야 할 n개의 숫자가 반의 반으로 줄어든다. 즉

k번 연산 후, 원하는 값을 찾았으므로 k번 연산 후 탐색해야 할 숫자의 개수는 한개이다. 즉

식을 정리하면, 

이다. 양변에 log2를 씌워주면,

이다. k가 연산 횟수이기때문에, 이진탐색의 복잡도는

가 된다.

예제

public class BinarySearch {
    public static void main(String args[]) {

        Scanner in = new Scanner(System.in);
        int key = Integer.parseInt(in.nextLine());
        String[] s = in.nextLine().split("\\s+");

        int n = s.length;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = Integer.parseInt(s[i]);
        }
        Arrays.sort(data);
        int result = binarySearch(data, key);

        System.out.println(result);

        in.close();
    }

    static int binarySearch(int arr[], int x) {
        int arrSize = arr.length;
        int upperBound = arrSize-1;
        int lowerBound = 0;
        int median;

        while(true){
            if(upperBound<lowerBound){
                return -1;
            }
            median = (upperBound+lowerBound)/2;

            if(arr[median]==x){
                return median;
            }else if(arr[median]>x){
                upperBound = median-1;
            }else{
                lowerBound = median+1;
            }
        }

    }

}