[알고리즘-PS] Java 에서 이진 검색 알고리즘을 구현하는 방법

이진 검색을 하기 위해 적용되는 전제 조건은 데이터가 키 값으로 정렬되어 있다는 가정에서 부터 시작합니다. 정렬 알고리즘의 학습이 필요한 사람은 선택 정렬 에 들어가서 가볍게 읽고 오시는 것을 추천드립니다.

이진 검색

이진 검색은 배열의 요소가 내림차순, 오름차순으로 정렬되어 있는 상태에서 검색을 진행하는 알고리즘 이다.

이진 검색의 배열을 절반으로 나눈 뒤 그 중간 값보다 크면 또 반으로 나누는 과정을 반복하여 원하는 값을 찾는 알고리즘이다..

이진 검색을 수행하기 전에 알아야 할 용어를 정의해보자.

start

배열의 시작 인덱스 (검색 범위의 시작)

center

배열의 중간 인덱스 (검색 범위의 중간)

end

배열의 끝 인덱스 (검색 범위의 끝)

 

 

이진 검색을 위해서 다음과 같이 정의 하였으면 이제 구동 원리를 알아보자.

 

이진 검색은 start와 end 사이의 center값과 검색하는 값을 비교하며 검색 값 보다 크면 start와 end, center를 서로 조절하여 값을 찾아내는 방법을 말 한다.

이진 검색의 검색 조건

모두 내림차순으로 정렬되어 있다고 가정하여 진행한다.

 

center < key 일 경우

이 경우는 start와 end 사이의 center의 값보다 key 값이 큰 경우를 뜻 한다.

그렇다면 start ~ center 사이에 값들을 제외하며 검색 범위를 center ~ end로 바꾸고 전 과정을 반복한다.

 

center > key 일 경우

이 경우는 start와 end 사이의 center의 값보다 key 값이 작은 경우를 뜻 한다.

그렇다면 center ~ end 사이에 값들을 제외하며 검색 범위를 start ~ center로 바꾸고 전 과정을 반복한다.

 

이진 검색의 종료 조건

모두 내림차순으로 정렬되어 있다고 가정하여 진행한다.

 

center == key 일 경우

이 경우는 start와 end 사이의 center의 값과 key의 값이 같을 때 이므로 검색을 종료한다.

 

start == end 일 경우

검색 조건을 반복한 결과 언젠가는 start 와 end 포인트가 같아지는 경우가 발생할 수 있는데 그 경우는 key 값이 해당 배열 안에 존재하지 않는다는 뜻 이므로 검색을 종료한다.

소스코드