[알고리즘] 이진검색

이진 검색 알고리즘(binary search algorithm)이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 
처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 
처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 
검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.
(위키백과 출처)
 
이진 검색은 검색을 반복할때마다 검색 범위가 반으로 줄어서 검색에 필요한 평균 횟수는 log n 입니다.
이진 검색은 정렬이 되어 있음을 가정합니다.

import java.util.*;

public class Test {

	static int binSearch(int [] a, int n, int key) {
		int pl = 0;		//검색 범위 첫 인덱스
		int pr = n-1;	//검색 범위 끝 인덱스
		
		do {
			int pc = (pl+pr)/2; //중앙 요소의 인덱스
			if(a[pc]==key) return pc;
			else if(a[pc]<key) pl=pc+1;
			else if(a[pc]>key) pr=pc-1;
		}while(pl<=pr);
		
		return -1; //검색 실패
	}
	
	public static void main(String[] args) {
			int [] arr =  new int [] {3,5,11,65,77,98,102,120,256 };
			int key=98;
			
			int idx=binSearch(arr, arr.length, key);
			
			if(idx==-1) System.out.println(key+"의 값이 배열에 없습니다.");
			else System.out.println(key+"값이 배열의 arr["+idx+"]에 있습니다.");
			
	}

}

실행 결과

 

자바로 코딩하였습니다.

 

Java는 이진검색을 표준라이브러리로 제공합니다.

java.util.Arrays 클래스의 binarySearch 메소드를 사용합니다.

public static void main(String[] args) {
			int [] arr =  new int [] {3,5,11,65,77,98,102,120,256 };
			int key=98;
			
			int idx=binSearch(arr, arr.length, key);
			
			System.out.println(Arrays.binarySearch(arr, key));
			
			
	}

결과값은 5가 나옵니다.

 

검색에 성공하면 key와 일치하는 요소의 인덱스를 반환합니다.

실패하면 -삽입포인트-1 이 나옵니다.