[JAVA] 이진 탐색, 이진 검색 (Binary Search)

이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다.

• 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법이다.
• 모든 원소는 정렬되어야 있어야 한다.

  ---

 

• 찾고자 하는 값이 arr[mid]인 경우 mid위치가 찾고자하는 값의 index 위치
• 찾고자 하는 값이 arr[mid]보다 작은 경우 mid 위치보다 왼쪽에 위치한다. 
• 찾고자 하는 값이 arr[mid]보다 큰 경우 mid 위치보다 오른쪽에 위치한다. 

---

출처 : 네이버 지식백과

출처 : 네이버 지식백과

 

---

소스코드

public class Ex04 {

	public static void main(String[] args) {
		int [] m = {1, 3, 8, 11, 15, 17, 20, 21, 25, 30, 34};
		int n = 21;	// 찾을 값 지정
		
		int idx = binarySearch(m, n);	// 함수
		
		if ( idx != -1) {
			System.out.printf("m[%d] 위치에 있습니다.",idx);
		} else {
			System.out.print("찾는 값이 없습니다.");
		}
	} //main

	private static int binarySearch(int[] m, int n) {	// 배열 m 중에서 찾을 값 n 입력 받는다. 
		int bottom = 0, top = m.length-1, middle;
		
		while ( bottom <= top ) {
			middle = (bottom + top) / 2;
			if ( m[middle] == n ) {	// 만약 중간 값이 찾고자 하는 값이라면
				return middle;
			} else if( m[middle] > n ){	// 찾고자 하는 값이 중간 값보다 작다면
				top = middle-1;
			} else if ( m[middle] < n ) {	// 찾고자 하는 값이 중간 값보다 크다면
				bottom = middle+1;
			}
		}
		return -1;	// 찾는 값이 없다면 -1을 가지고 return
	} //binarySearch

} //class