Binary Search(이진분류)구현

Binary Saerch

• 정렬되어 있는 숫자들 중에서 특정 숫자를 찾는다. (시간 복잡도 O(log(n))

• Binary Search는 이미 정렬되어 있는 배열에서 효율적으로 숫자를 찾을 수 있다.

• 일반 2중 for문을 이용한다면 시간 복잡도가 O(log(n))인 반면, Binary Search는 시간 복잡도가 O(log n) 이므로 배열의 크기가 클수록 걸리는 시간이 줄어들게 된다.

Binary Serach 구현 방법
1. 재귀호출을 이용한 구현

2. 재귀호출을 이용하지 않는 구현

재귀 함수를 이용한 구현

#include <stdio.h>

int BinarySearch(int start, int end , int arr[] , int value){
// arr의 start 부터 end 까지 값들 중에서 value가 존재하면
// 그때의 index를 반환하고, 존재하지 않으면 -1을 반환

// 기저 조건 : 숫자가 하나도 남지 않거나, 
// 숫자가 한개가 남거나
  if(start > end) return -1;
  else if(start == end){
    if(arr[start] == value) return start;
    else return -1;
  }
  
  else{
    int mid = (start + end)/2;
    if(arr[mid] == value) return mid;
    else if(arr[mid] > value) BinarySearch(start , mid-1 , arr, value);
    else BinarySearch(mid+1 , start , arr , value);
  }
}

int main() {

  int n; // 배열 크기
  int value; // 찾고자 하는 숫자
  int arr[100];
  scanf("%d" , &n);
  for(int i = 0  ; i < n ; i++) scanf("%d" , &arr[i]);
  
  scanf("%d" , &value);
  
  int idx = BinarySearch(0 , n-1 , arr , value);
  if(idx == -1) printf("수가 없습니다. \n");
  else printf("%d번째에 숫자가 있습니다. \n" , idx);
  
  return 0;
}

문제

n개의 오름차순으로 정렬된 숫자가 주어지고, 그 후 q개의 질문이 주어진다. 각각의 질문은 특정 숫자가 n개의 숫자 내에 존재하는지를 판별하는 것이다. 모든 q개의 질문에 대하여 답을 하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 이는 오름차순으로 정렬되어 주어진다. 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 각 수는 21억보다 작은 정수다.

---

출력

각 질문에 대하여 숫자가 존재하면 YES, 아니면 NO를 한 줄에 하나씩 출력한다.

---

예제 입력
10 4
1 2 4 8 10 11 12 14 15 19
4 5 8 17

예제 출력
YES
NO
YES
NO

---

#include <stdio.h>
int BinarySearch(int arr[] , int start , int end , int value){
  if(start > end) return -1;
  else if(start == end){
    if(arr[start] == value) return start;
    else return -1;
  }
  else{
    int mid = (start + end) /2;
    if(arr[mid] == value) return mid;
    else if(arr[mid] > value){
      BinarySearch(arr , start , mid-1 , value);
    }
    else BinarySearch(arr , mid+1 , end , value);
  }
}
int main() {
  int arr[100001];
  int value;
  int n, q;
  scanf("%d %d" , &n , &q);
  for(int i = 0 ; i < n ; i++)
    scanf("%d" , &arr[i]);
  
  for(int i = 0 ; i < q ; i++){
    scanf("%d" , &value);
    int idx = BinarySearch(arr , 0 , n-1 , value);
    
    if(idx != -1)
    printf("YES\n");
    else
    printf("NO\n");
  }
  return 0;
}