이진검색1 [Java] 이진검색(BinarySearch) 이진 검색은 데이터가 키 값으로 이미 정렬되어 있을 때 적용할 수 있는 알고리즘이다. 이진검색의 시간복잡도는 O(log N) 이다. 전체 범위를 탐색하는 선형 검색과 달리 검색 범위를 1/2로 줄여가면서 찾아가는 방법이다. 아래와 같이 7개의 요소를 가지는 배열에서 값이 23인 요소의 인덱스를 찾는 과정을 살펴보자. 1. 먼저 중앙값을 검색한다. 2. 중앙값과 타겟값을 비교한다. 중앙값인 15가 타겟인 23보다 작으므로 값이 작은 왼쪽 부분은 탐색하지 않고 오른쪽 부분만 탐색한다. 만약 타겟이 15였다면 더 이상 검색을 하지 않고 종료되었을 것이다. 이처럼 크기 비교 결과에 따라 검색 범위가 달라지므로 이미 정렬되어 있는 대상에만 적용할 수 있다. 3. 타겟을 찾을때까지 1과 2의 과정을 반복한다. 위 .. 2023. 4. 19. 이전 1 다음
