목록바이너리서치 (1)

공부기록

이진 탐색(binary search)

이진탐색'정렬된 리스트'에서 특정 값을 빠르게 찾는 알고리즘.리스트를 반으로 나눠서 목표값이 어느 쪽 절반에 속하는지 결정하고, 나머지 절반은 버리면서 목푯값이 포함될 가능성이 있는 절반을 탐색한다.값을 찾을 때까지 이 과정을 반복한다. 어느 쪽에 속해야하는 지 결정해야하기 때문에 기본적으로 정렬된 리스트여야한다.배열 A 에서 i A[i] 문제 정의다음과 같은 오름차순으로 정렬된 배열 A 가 있다.[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 배열 A 에서 숫자 10을 찾아보자.문제 해결앞서 말한 것처럼 이진 탐색은 리스트를 반으로 나누어 탐색하기 때문에 탐색공간의 중앙값을 선택하며 시작해야한다. 이를 코드로 나타내면 다음과 같다.var indexHigh = list.size - 1 // 탐..
Computer Science/자료구조 2024. 12. 23. 12:49
이전 Prev 1 Next 다음