성장 일기/알고리즘
2021. 8. 17.
[JAVA]이진 탐색(Binary Search)
이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 1/2씩 줄여가며 데이터를 탐색하는 방법. * 이진 탐색을 수행할 때는 탐색 범위를 명시해야한다. 따라서 시작점과 끝점 그리고 중간점을 이용하여 탐색한다. 예를 들어보자, 다음 정렬되어 있는 리스트에서 있는 5를 탐색하는 경우는 다음과 같다. 중간 인덱스 값은 리스트의 길이의 1/2 값을 사용한다. 리스트의 길이가 홀수라면 1/2값에서 소수첫째자리에서 버림한 값을 사용한다. 다음은 리스트에 없는 값인 2를 탐색하는 경우이다. 없는 값을 탐색하는 경우 더 이상 남은 항목이 없으면 탐색 실패로 -1를 리턴해준다. 이제 이진탐색의 코드를 확인해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..
