[Java] 알고리즘 Day7

이진 탐색

순차 탐색

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

순차 탐색

순차 탐색 자바 코드 구현

// 순차 탐색 소스코드 구현
public static int sequantialSearch(int n, String target, String[] arr) {
    // 각 원소를 하나씩 확인하며
    for (int i = 0; i < n; i++) {
        System.out.println(arr[i]);
        // 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if (arr[i].equals(target)) {
            return i + 1; // 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기)
        }
    }
    return -1; // 원소를 찾지 못한 경우 -1 반환
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 원소의 개수
    int n = sc.nextInt();
    // 찾고자 하는 문자열
    String target = sc.next();
    
    String[] arr = new String[n];
    for (int i = 0; i < n; i++) {
        arr[i] = sc.next();
    }

    // 순차 탐색 수행 결과 출력
    System.out.println(sequantialSearch(n, target, arr));
}

 

이진 탐색

• 반으로 쪼개면서 탐색하기
• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
• 배열이 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음
• 시작점, 끝점, 중간점을 사용하여 탐색
• 찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교해서 원하는 데이터를 찾음

재귀를 활용한 이진 탐색

// 이진 탐색 소스코드 구현(재귀 함수)
public static int binarySearch(int[] arr, int target, int start, int end) {
    if (start > end) return -1;
    int mid = (start + end) / 2;
    // 찾은 경우 중간점 인덱스 반환
    if (arr[mid] == target) return mid;
    // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
    // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else return binarySearch(arr, target, mid + 1, end);
}

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

    // 원소의 개수(n)와 찾고자 하는 값(target)을 입력받기 
    int n = sc.nextInt();
    int target = sc.nextInt();

    // 전체 원소 입력받기 
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }

    // 이진 탐색 수행 결과 출력 
    int result = binarySearch(arr, target, 0, n - 1);
    if (result == -1) {
        System.out.println("원소가 존재하지 않습니다.");
    }
    else {
        System.out.println(result + 1);
    }
}

 

반복문을 사용한 이진 탐색

// 이진 탐색 소스코드 구현(반복문)
public static int binarySearch(int[] arr, int target, int start, int end) {
    while (start <= end) {
        int mid = (start + end) / 2;
        // 찾은 경우 중간점 인덱스 반환
        if (arr[mid] == target) return mid;
        // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        else if (arr[mid] > target) end = mid - 1;
        // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else start = mid + 1; 
    }
    return -1;
}

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

    // 원소의 개수(n)와 찾고자 하는 값(target)을 입력받기 
    int n = sc.nextInt();
    int target = sc.nextInt();

    // 전체 원소 입력받기 
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }

    // 이진 탐색 수행 결과 출력 
    int result = binarySearch(arr, target, 0, n - 1);
    if (result == -1) {
        System.out.println("원소가 존재하지 않습니다.");
    }
    else {
        System.out.println(result + 1);
    }
}

 

코딩 테스트에서 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제 접근해보기

 

트리 자료구조

이진 탐색 트리

• 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
• 부모 노드보다 왼쪽 자식 노드가 작음
• 부모 노드보다 오른쪽 자식 노드가 큼
  • 왼쪽 자식 노드 <  부모 노드 < 오른쪽 자식 노드