이진탐색1 이진 탐색(Binary Search) (Java) 이진 탐색이란? "정렬된 배열"에서 특정한 값을 찾아내는 알고리즘 배열의 중간 값과 찾고자 하는 값을 비교하면서 탐색한다. 찾고자 하는 값이 X라고 하면, X가 중간 값보다 작으면 좌측 데이터를 대상으로, X가 중간 값보다 크면 우측 데이터들을 대상으로 다시 탐색한다. 해당 과정을 X를 찾을 때까지 반복한다. 시간 복잡도 전체 데이터 수를 N이라고 하자. 1) 첫 번째 탐색 후 절반만 남아 남은 수가 N/2개 2) 두 번째 탐색에서 다시 절반만 남아 남은 수가 N/2 ×1/2개 3) 세 번째 탐색에서 다시 절반이 남아 남은 수가 N/2 ×1/2 ×1/2개 ... k) 규칙을 찾아보면 k번째 탐색에서 남은 데이터 수는 (1/2)^k * N이 된다. 최고의 경우 중간 값이 찾고자 하는 값인 경우에는 한 번에.. 2023. 5. 3. 이전 1 다음
