이진 탐색 (Binary Search)
2022.04.14
탐색 과정 이진 탐색(Binary Search) 알고리즘은 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 먼저 이 알고리즘은 반드시 정렬을 한 후에 탐색을 시작해야 한다. 탐색할 범위의 시작과 끝이 같은 경우에는 찾지 못한 것으로 본다. 그렇지 않은 경우에는 탐색할 범위의 중간값을 확인하여 찾고자 하는 값보다 크거나 작은지 확인한다. 만약 값이 같다면 검색에 성공하여 위치를 반환하고 탐색을 종료한다. 중앙값이 찾는 값보다 크면 새로운 최댓값으로, 작다면 새로운 최솟값으로 설정하여 다시 탐색을 시작한다. 반드시 정렬을 해야한다는 단점이 있지만, 검색을 반복할 때마다 탐색할 범위가 1/2로 줄어들기 때문에 탐색 속도가 빠른 편이다. 구현 코드 import java.util.Scanner; public c..