[알고리즘] 이진 탐색

이진 탐색이란?

데이터가 정렬돼 있는 배열에서 특정한 값을 찾는 알고리즘이다

 

쉽게 대학생 때 술자리에서 소주 뚜껑에 쓰여있던 숫자로 했던 업다운 게임을 푸는 알고리즘이라고 생각하면 된다

 

이진 탐색은 소주 뚜껑에 1~10까지의 숫자가 쓰여있다고 가정할 때 정중앙인 5나 6을 먼저 질문하고

답이 아니라면 또다시 가능한 숫자 중에 정중앙에 있는 숫자를 질문하는 방식이다

 

이진 탐색 개념

그림으로 그려보면 아래와 같다

 

 

자, 2는 어디 있을까?

모든 숫자가 빠짐없이 나열되어 있으니 너무 당연해 보인다

그렇다면 숫자가 중간중간 빠져있다면 어떨까?

 

 

7은 어디에 있을까?

컴퓨터한테 앞에서부터 순서대로 찾으라고 시켜야 될까?

아니다 이건 너무 느리다

이진탐색을 활용해서 좀 더 빠르게 찾아보자

 

먼저 중간 지점(2개일 경우 둘 중 하나)을 먼저 확인하자

 

 

중간 지점의 값이 우리가 찾는 7인가?

그렇다면 찾은 것이고 아니라면 다음 작업을 진행한다

 

중간 지점의 값이 7보다 큰가?

크다면 왼쪽에 값 중에서 7을 다시 찾을 것이고

작다면 오른쪽에 값 중에서 7을 다시 찾을 것이다

 

이 경우엔 4<7이므로 오른쪽 값들을 보자

 

 

여기서부터 반복이다!

남아있는 값 중에서 중앙값을 다시 보자

 

 

7을 찾았나?

아니라면 7보다 큰가? 작은 가?

8>7이므로 이번엔 왼쪽을 보자

 

 

다시 반복한다!

남아있는 값 중에서 중앙값을 다시 보자

 

 

7을 찾았나?

네, 드디어 찾았다

이제 해당 값의 위치를 기억하면 된다

 

한글 코딩

이진 탐색을 실제로 코딩하기 전에 한글로 의사코딩을 해보자

 

datas = 테스트용 정수 배열 정의
findNum = 찾고 싶은 값

// 반복문을 돌며 각 영역에서 중간 값을 확인할 것이다
// 영역은 그때 그때 달라지므로 영역의 시작 위치와 마지막 위치를 알아야 한다
시작 위치, 마지막 위치 초기화
findIdx 찾은 위치를 저장할 변수
반복문 () {
    중간 위치 = (시작 위치 + 마지막 위치) / 2
    if (중간 값 == 찾는 값) {
    	찾았다!!
        findIdx = 찾은 위치
        break ;
    } else if (중간 값이 찾는 값보다 작은 경우) {	// 찾는 값이 중간 값보다 더 오른쪽에 있다
    	시작 위치 = 중간 값 + 1
    } else if (중간 값이 찾는 값보다 큰 경우) {		// else를 써도 된다
    	마지막 위치 = 중간 값 - 1;
    }
}

잘 찾았는지 출력해보기!

 

실제 코딩

package binary_search;

public class blogging01 {

	public static void main(String[] args) {

		int[] datas = {1, 2, 4, 7, 8, 10};
		int findNum = 7;
		
		int start = 0;
		int end = datas.length - 1;
		int findIdx, mid;
		
		while (true) {
			mid = (start+end)/2;
			if (datas[mid] == findNum) {
				findIdx = mid;
				break ;
			} else if (datas[mid] < findNum) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		
		System.out.printf("찾는 값: %d, 찾은 값: %d, 찾은 위치: %d\n", findNum, datas[findIdx], findIdx);
	}
}

 

잘 동작함을 확인할 수 있고

추가로 7이 없는 경우와 배열이 정렬되지 않은 경우에도 while문을 탈출할 수 있게 짜면 더 좋을 거 같다

끝!