탐색 | 순차 탐색, 이진 탐색, 부품 찾기

순차 탐색 / 이진 탐색

순차 탐색

• 배열 안에 있는 특정 데이터를 찾기 위해 앞으로 데이터를 하나씩 차례대로 확인하는 방법이다.
• 정렬되지 않은 배열에서 특정 데이터를 찾고자 할 때 사용한다.
• 데이터가 아무리 많아도 시간이 충분하다면 항상 원하는 데이터를 찾을 수 있다는 장점이 있다.
• 제일 처음 인덱스부터 순차적으로 탐색하기 때문에 시간 복잡도는 **O(N)** 이다. (N = 배열의 길이)
• (뭔가 버블 정렬과 비슷한 알고리즘 같다.)

이진 탐색

• 배열이 정렬되어 있다는 전제 하에 사용할 수 있는 알고리즘이다.
• 시작점과 끝점을 이용해 중간점을 찾고, 찾고자 하는 데이터와 중간점의 데이터가 맞을 때 까지 반복한다.
• 즉, 재귀 함수 또는 반복문을 통해 구현할 수 있다.
• 탐색 범위를 절반씩 줄여 나가기 때문에 빠른 시간 내에 탐색을 마무리 할 수 있다.
• 단, 배열 내 중복된 데이터가 있을 경우 최선의 알고리즘은 아니다.

Lower / Upper Bound

• 이진 탐색의 경우 중복 데이터가 존재하지 않을 경우 최선이지만, 중복 데이터가 존재할 경우 최선이 될 수 없다. 이를 보완하기 위해 나온 알고리즘이 Lower / Upper Bound 알고리즘이다.

Lower Bound

• 찾고자 하는 데이터와 같거나 가장 가까운 크기의 데이터의 인덱스를 반환한다.
• 즉, Lower Bound를 통해 반환된 인덱스 번호 이후에 데이터는 몇 개인지는 모르지만 중복된 데이터가 존재한다는 의미이다. (이를 보완하기 위해서 Upper Bound 알고리즘을 활용한다.)
• 그러한 이유로 반환된 인덱스 번호 이전의 인덱스에는 절대 해당 데이터는 배열 내에서 존재하지 않는다.
• 만약 찾고자 하는 데이터가 배열 내에 존재하지 않을 경우 찾고자 하는 데이터와 가장 근접한 데이터의 인덱스 번호를 반환한다.

Upper Bound

• 찾고자 하는 데이터가 배열 내에서 몇 개가 존재하는지 모르는 Lower Bound 알고리즘을 보완하기 위해서 만들어진 알고리즘이다.
• Upper Bound 알고리즘은 찾고자 데이터의 가장 가까운 초과된 데이터가 존재하는 인덱스 번호를 반환한다.

참고 블로그

이진탐색-상/하한선((lower bound,upper bound)

이진 탐색을 응용해서 문제 해결하기

부품 찾기 - 이코테

package 심성헌.알고리즘_5주차.이코테;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 부품찾기_이코테 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, m;
    static int[] arr1, arr2;

    public static void main(String[] args) throws Exception {
        // N = 물건의 개수 / M = 내가 찾는 물건의 개수
        // N 입력
        n = Integer.parseInt(br.readLine());
        arr1 = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        int idx = 0;
        while (st.hasMoreTokens()) {
            arr1[idx] = Integer.parseInt(st.nextToken());
            idx++;
        }

        // M 입력
        m = Integer.parseInt(br.readLine());
        arr2 = new int[m];
        st = new StringTokenizer(br.readLine());
        idx = 0;
        while (st.hasMoreTokens()) {
            arr2[idx] = Integer.parseInt(st.nextToken());
            System.out.print(find(arr1, 0, n - 1, arr2[idx]) + " ");
            idx++;
        }
    }

    public static String find(int[] arr, int start, int end, int target) {
        if (start > end) return "No";
        int mid = (start + end) / 2;
        if (arr[mid] == target) return "Yes";
        else if (arr[mid] > target) return find(arr, start, mid - 1, target);
        else return find(arr, mid + 1, end, target);
    }
}

이번 문제는 비교적 쉽게(?) 풀 수 있었던 것 같다.
다만 주어진 테스트 케이스에서 마지막 출력값이 Yes 로 출력되어야 하는데 자꾸 No 로 출력되어서 왜 이런지 이유를 찾는데 시간이 꽤나 소요됐다.

find 메소드는 String 자료형을 반환하는데, else if 구문에서 재귀로 find 메소드를 호출하게 해놓고서는 이걸 return 해주지 않는 정말 사소한 문제때문에 시간이 오래 소요됐다. 맞다. 나 바보다.