[알고리즘] 이진검색

이진검색?

대학교 신입생 때 술자리에서 소주 병뚜껑을 가지고 하던 업다운 게임을 해본적이 있다면 아마 이진검색은 쉽게 이해할 수 있을 것이다.

처음부터 무식하게 하나씩 비교하는 순차탐색과는 다르게 이진검색을 하기 위해선
데이터가 정렬되어있어야 한다. 오름차순이든 내림차순이든 상관없다. 이런 전제조건이 필요하기에 연결리스트에는 적합하지 않다고 한다.

이진검색은 선형검색보다 수행횟수가 현저히 작아진다. 정렬만 되어있다면 빠른 검색법이다.

방법은 간단하다.
요소의 개수가 n인 배열 a가 있다. 이 배열 a의 값들은 일정하게 정렬이 되어있다. 지금은 오름차순으로 가정한다. 이 중 나는 key라는 값을 찾고 싶다.

• startIndex = 검색할 범위의 시작인덱스, 처음은 0
• endIndex = 검색할 범위의 끝인덱스, 처음은 n-1
• center = (startIndex + endIndex) / 2 => 검색할 범위의 중간값
• 검색할 범위의 요소들 개수가 홀수라면 정확히 가운데 값이 존재하지만 짝수여도 문제가 없다. 정수 / 정수는 따로 캐스팅을 해주지 않으면 소수점을 버리고 정수가 나온다.

1. a[center]이 key와 같은가? 같으면 검색성공! 하지만 다르다면...
2. a[center] > key 일때, 배열 a는 오름차순으로 정렬되어 있으므로 찾으려는 key는 center보다 작은 범위들을 찾아야 있다. 끝범위 endIndex를 center-1로 바꿔준다.
3. a[center] < key 일때, 반대로 startIndex가 center+1이 되어야 겠다.
4. 위 3단계를 반복한다.

import java.util.Scanner;

public class BinSearch {
	static int binSearch(int[] a, int n, int key) {
		int startIndex = 0; //검색범위 시작 인덱스
		int endIndex = n-1; //검색범위 끝 인덱스
		int center = (startIndex + endIndex) / 2;
		while(startIndex <= endIndex) {
			//검색에 성공하였을 때!
			if(a[center]==key) {
				return center;
			}
			//검색의 범위를 center를 기준으로 나눔
			if(a[center]>key) {
				endIndex = center - 1;
			} else if(a[center]<key) {
				startIndex = center + 1;
			}
			
			center = (startIndex + endIndex) / 2;
		}
		//만일 while문을 빠져나왔다면 일치하는 값이 없는것
		return -1;		
	}
	
	public static void main(String[] args) {
		Scanner ss = new Scanner(System.in);
		System.out.println("배열의 요소 개수 입력 : ");
		int num = ss.nextInt();
		int[] arr = new int[num];
		
		for(int i=0; i<num;i++) {
			System.out.print("arr["+i+"]: ");
			arr[i] = ss.nextInt();
		}
		
		System.out.println("찾고싶은값(key) 입력 : ");
		int key = ss.nextInt();
		
		int index = binSearch(arr, num, key); 
		
		if(index == -1) {
			System.out.println("찾는값이 배열에 없습니다.");
		} else {
			System.out.println("찾는 값은 arr["+index+"]에 있습니다.");
		}
		ss.close();
	}
}

표준라이브러리 이진탐색

java에서는 표준라이브러리로 이진탐색 메서드를 제공한다.
java.util.Arrays에 구현이 되어있으므로 이진탐색이 필요하다면 그냥 가져다가 쓰면 된다.

배열과 찾으려는 key값을 넣어주면 만약 찾는 값이 있다면 배열의 인덱스를 반환하고, 없다면 삽입포인트를 반환해주는데 이게 음수값이다.