[알고리즘] Binary search (이분 탐색)

🔍 Learn

Binary Search (이분 탐색 / 이진 탐색)

Binary Search 알고리즘은 정렬된 배열에서 특정 값을 찾는 알고리즘으로, 시간복잡도는 O(logN)이다.

📌 알고리즘

이분 탐색은 내가 찾고자 하는 값(key)과 배열의 중간 값을 비교한다. 이 때, key가 더 크다면, 중간 값 이후의 값들만이 탐색 대상이 된다. 반대로, key가 더 작다면, 배열의 중간값 이전의 범위가 다음 탐색의 범위가 되는 것이다.

이렇게 탐색의 범위를 1/2씩 줄여 나간다. (시간복잡도가 logN이 되는 이유)

1. 중간 인덱스 구하기
2. 내가 찾는 값과 중간 값 비교하기
3. 다음 탐색 범위 정하기
   -> 반복

관련 문제

: BOJ 1920 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

💻 Code

이분 탐색 알고리즘 -> binarySearch 메소드

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

public class BJ_1920 {
  public static boolean binarySearch(int[] arr, int x){
      int lo=0, hi=arr.length-1;

      while(lo <= hi){
          int mid=(lo+hi)/2;

          if(x < arr[mid]){
              hi = mid-1;
          }
          else if(x > arr[mid]){
              lo = mid+1;
          }
          else{
              return true;
          }
      }

      return false;
  }

  public static void main(String[] args) throws IOException {
      BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
      StringBuilder sb = new StringBuilder();
      int N, M;

      N = Integer.parseInt(bf.readLine());
      int[] arr = new int[N];

      StringTokenizer st = new StringTokenizer(bf.readLine());

      for(int i=0; i<N; i++){
          arr[i] = Integer.parseInt(st.nextToken());
      }

      Arrays.sort(arr);

      M = Integer.parseInt(bf.readLine());
      st = new StringTokenizer(bf.readLine());

      for(int i=0; i<M; i++){
          int x = Integer.parseInt(st.nextToken());
          if(binarySearch(arr, x))
              sb.append(1 + "\n");
          else
              sb.append(0 + "\n");
      }

      System.out.print(sb);
  }
}