이진 탐색 - 백준 수 찾기

2022.04.18 - 04.22

과제 : 이진 탐색에 관련된 문제 풀기

진행 : Google Meet를 통한 코드리뷰 진행

• 이진 탐색(Binart search)이란?
  • 예 시 : 많은 카드 숫자들 중 원하는 숫자를 찾고 싶을 떄, 모든 카드를 다 뒤집어 보는 것 보다 몇 장의 카드들만 뒤집어서 원하는 숫자를 찾을 수 있다.
  • 정렬되어 있는 데이터 집합을 두 급으로 나누어 가며 원하는 key값을 찾는 탐색
  • 데이터는 내림차순(5,4,3,2,1) 혹은 오름차순(1,2,3,4,5)으로 정렬
• 이진 탐색 과정
  • ({4,15,2,3,7,6} 중 5를 찾는 과정)

         1.{1,2,3,4,5,6,7} 오름차순으로 정렬

         2. 중간 값 4와 key 값 5가 같은지 비교

         3. 중간 값 4가 key 값 5보다 작으므로 오른쪽에 위치한 데이터들을 기반으로 이진 탐색을 진행

         4. 중간 값 6이 key 값 5와 같은 지 비교한다.

         5. 중간 값 6이 key 값 5보다 크므로 왼쪽에 위치한 데이터를 기반으로 이진 탐색을 진행

 

         6. 중간 값 5가 key 값 5 와 같은 지 비교한다. 같으므로 탐색 성공 

 

•  시간 복잡도
  • 최상의 경우 : O(1)
    • Key값이 탐색을 진행할 때 중간 값으로 두 그룹으로 나누지 않고 바로 찾은 경우
      (예시 : 위 과정에서 4를 찾는 과정)
  • 최악의 경우 : O(log n)
    1. 이진 탐색을 반복할 수록 자료의 갯수가 절반이 된다. 예를 들어, 탐색할 데이터의 갯수가 n이면
    2. 1 번 시행 후 : n/2
    3. 2 번 시행 후 : n/2 * 1/2
    4. 3 번 시행 후 : n/2 *1/2*1/2
    5. k 번 시행 후 : n * 1/2^k ≒ 1 (k번 시행 후 남은 데이터의 갯수는 1개이다.)
    6. 양 변에 2^k를 곱해주면 n ≒ 2^k가 되고 양 변에 log를 씌워주면
    7. k ≒ logn

 

• left , right, mid 초기 값을 0과 맨 마지막 값을 입력한다.
  • mid 값의 경우 (right - left) / 2를 사용해도 되지만, (2^31)-1범위를 넘어가게 되면 -1값을 반환하기 때문에 left + (right-left) / 2로 해주었습니다. (2^31)-1넘어가지 않으면 위의 식을 써도 상관 없습니다!

int left = 0;
int right = Narr_size-1;
int mid = left + (right - left) / 2;

 

• Key값 탐색 실패 : 이진 탐색을 계속 시행하다 보면, 원하는 값이 나오지 않을 때는 left > right 되는 상황이 된다.

if( left > right)
	return -1;​

• Key 탐색 성공 : 원하는 값을 찾았으므로 해당 주소를 반환해 줍니다.

if( arr[mid] == key )
	return mid;

• 중간 값이 key 값 보다 작을 경우
  • 중간 값에 오른쪽으로 탐색영역을 새로 설정해 줘야합니다
  • left = mid +1, right : 유지

else if( arr[mid] < key)
	return binary_search(arr, mid+1, right, key);

•  중간 값이 key 값 보다 클 경우
  • 중간 값에 왼쪽으로 탐색영역을 새로 설정해 줘야합니다.
  • left : 유지, right = mid - 1

else return binary_search(arr, left, mid-1, key);

 

•  전체적인 코드

• public static int binary_search(int[] arr, int left, int right, int key) {
  		
  		// 이진 탐색 종료 조건1(탐색 실패..ㅠ 0을 반환)
  		if( left > right)
  			return 0;
  		int mid = left + (right - left) / 2;
  		
  		//이진탐색 종료 조건 2(탐색 성공! 1을 반환)
  		if( arr[mid] == key )
  			return 1;
  		// 중간 원소보다 값이 크면 오른쪽
  		else if( arr[mid] < key)
  			return binary_search(arr, mid+1, right, key);
  		
  		// 중간 원소보다 값이 작으면 왼쪽
  		else
  			return binary_search(arr, left, mid-1, key);

 

• 수 찾기 (문제 백준 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을 출력한다.

  예제 입력 1 복사

  5
  4 1 5 2 3
  5
  1 3 7 9 5
  

  예제 출력 1 복사

  1
  1
  0
  0
  1

• 구현 코드

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

public class Main{
		
	static int Narr_size;
	static int Marr_size;


	
	public static void main(String[] args) throws IOException  {
		
		int[] Narr;
		int[] Marr;
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 비교 N 배열의  사이즈 입력받기
		Narr_size = Integer.parseInt(st.nextToken()); 
		Narr = new int[Narr_size]; 
		
		
		
		// 비교 N 배열의 원소값 입력
		st = new StringTokenizer(br.readLine()); 
		for(int i = 0; i < Narr_size; i++) 
			Narr[i] = Integer.parseInt(st.nextToken()); 
		
		// 비교 M 배열의 사이즈 입력
		st = new StringTokenizer(br.readLine());
		Marr_size = Integer.parseInt(st.nextToken());
		Marr = new int[Marr_size];
		
		// 비교 M 배열의 원소값 입력
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i<Marr_size; i++) 
			Marr[i] = Integer.parseInt(st.nextToken());
			
		//-----------------------입력--------------------
		solution(Narr, Marr);

	}
	
	
	public static void solution(int[] Narr, int[] Marr) { 
		
		int left = 0;
		int right = Narr_size-1; 
		
		//이진 탐색을 사용하기 위해 오름차순으로 정렬
		Arrays.sort(Narr);
		
		//M 배열의 원소들이 N 배열에 있는 지 탐색
		for(int i = 0; i < Marr_size; i++) 
			System.out.println(binary_search(Narr, left, right, Marr[i]));

		
		
	}
	// 재귀를 이용한 이진탐색
	public static int binary_search(int[] arr, int left, int right, int key) {
		
		// 이진 탐색 종료 조건1(탐색 실패..ㅠ 0을 반환)
		if( left > right)
			return 0;
		int mid = left + (right - left) / 2;
		
		//이진탐색 종료 조건 2(탐색 성공! 1을 반환)
		if( arr[mid] == key )
			return 1;
		// 중간 원소보다 값이 크면 오른쪽
		else if( arr[mid] < key)
			return binary_search(arr, mid+1, right, key);
		
		// 중간 원소보다 값이 작으면 왼쪽
		else
			return binary_search(arr, left, mid-1, key);
			
		
	}
	
	
}

/*
 이진 탐색의 시간 복잡도 
 best - O(1)
 average - Θ(log n)
 worst - O(log n)
*/

가장 기초적인 이진 탐색 문제 였습니다. 두 번째 줄 원소들을 Narr[] 에 넣어 오름차순으로 정렬 한 뒤 반복문을 통해 

네 번째 원소들을 넣은 Marr[] 원소들 binary_search 에 넣어줘 해당 하는 값이 있으면 1을 반환, 없으면 0을 반환한도록 하게 하였습니다.