[알고리즘] 이진탐색

1. 개념설명(특징, 사진 등)
2. 사용 방법(코드 설명)
3. 언제 사용하는가?
4. 예제

🌈 이진탐색 개념

• 배열 중앙에 있는 값을 구하여 왼쪽 혹은 오른쪽 배열에 찾고자 하는 값이 있는지 알아내어 탐색 범위를 반으로 줄인다.
• 데이터의 삽입이나 삭제가 빈번할 때는 적절하지 않고, 고정된 데이터에 대한 탐색에 적합하다.

☁ 사용방법

반복문

public static int binarySearch(int arr[], int find) {
  int mid;
  int left = 0;
  int right = arr.length - 1;

  // 배열의 크기가 1이 될 때까지 반복.
  while (left <= right) {
    mid = (right + left) / 2;

    // 원하는 값을 찾았다면 그 위치를 반환.
    if (arr[mid] == find) {
      return mid;
    }

    if (find < arr[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  // 원하는 값을 찾지 못함.
  return -1;
}

재귀

public static int binarySearch(int[] arr, int find, int left, int right) {
  // 원하는 값을 찾지 못함.
  if (left > right) {
    return -1;
  }

  int mid = (left + right) / 2;
  
  // 원하는 값을 찾았다면 그 위치를 반환.
  if (find == arr[mid]) {
    return mid;
  }

  if (find > arr[mid]) {
    return binarySearch(arr, find, mid + 1, right);
  }
  return binarySearch(arr, find, left, mid - 1);
}

🎪 언제 사용하는가?

ex) 10억 명이 정렬된 배열에서 이진 탐색을 이용하면 단 30번의 비교만으로 검색이 완료된다. 반면 순차 탐색의 경우 평균 5억번의 비교가 필요하다.

ex) 영어 사전에서 단어를 찾는 과정에 사용된다. 영어 사전을 펼쳐 찾고자 하는 단어가 현재 페이지보다 앞에 있는지, 뒤에 있는지 결정한 다음, 단어가 있는 부분 만을 검색한다.

🚀 예제

백준_1920

N개의 수를 가진 배열 A[ ]를 입력하고 다른 입력받은 M개의 숫자들이 배열 A[ ] 안에 존재하는지 출력하는 문제이다. 존재하면 1, 존재하지 않으면 0을 출력한다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A[] = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        Arrays.sort(A); //정렬
        int M = sc.nextInt();
        int find[] = new int[M]; //찾아야할 수
        int Answer[] = new int[M]; //1, 0을 출력
        for (int i = 0; i < M; i++) {
            find[i] = sc.nextInt();
        }
        for (int i = 0; i < M; i++) {
            int start = 0;
            int end = A.length - 1;
            while (start <= end) {
                int mid = (start + end) / 2;
                if (find[i] > A[mid]) {
                    start = mid + 1;
                } else if (find[i] < A[mid]) {
                    end = mid - 1;
                } else if (find[i] == A[mid]) {
                    Answer[i] = 1;
                    break;
                } else {
                    Answer[i] = 0;
                    break;
                }
            }
        }
        for (int j = 0; j < M; j++) {
            System.out.println(Answer[j]);
        }
    }
}

참고 : https://steady-coding.tistory.com/229