이진 탐색 (Binary Search)

이진 탐색 (Binary Search)

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
• 목적 키를 찾을 때까지 이진 탐색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함
  
• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

검색 과정

1. 자료의 중앙에 있는 원소를 고른다.
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
3. 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 끝낸다.
4. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 탐색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
5. 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.
   예) 이진 탐색으로 7을 찾는 경우
   
   예) 이진 탐색으로 23을 찾는 경우
   
   예) 이진 탐색으로 20을 찾는 경우
   

알고리즘 : 반복구조

binarySearch(S[], n, key)
	start <- 0
    end <- n -1
 	
    WHILE start <= end
    	mid <- (start + end) / 2
        IF S[mid] == key
        	RETURN mid
        ELIF S[mid] < key
        	start <- mid + 1
        ELIF S[mid] > key
        	end <- mid - 1
     END WHILE
     RETURN -1

알고리즘 : 재귀구조

binarySearch(S[], start, end, key)
	IF start > end
    	RETURN -1
 	
    ELSE
    	mid <- (start + end) / 2
        IF S[mid] == key
        	RETURN mid
        ELIF S[mid] < key
        	RETURN binarySearch(S[], mid + 1, end, key)
        ELSE
        	RETURN binarySearch(S[], start, mid - 1, key)

이진 탐색 API

java.util.Arrays.binarySearch

• 이진 탐색 API
• int binarySearch(int[] a, int key)
• int binarySearch(int[] a, int fromIndex, int toIndex, int key)
• https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html