자유롭게 이야기를 적는 공간
글 수 15,183
이진 검색 강의
릭*보는 사람을 고려하지 않았습니다.
배열이 1에서 N개가 있다면(이걸 a(i)라고 둡시다)
물론 이 배열은 오름차순으로 정렬 되어 있어야 합니다.
일단 L=1,R=N로 둡니다.
그다음 중간값인 (L+R)/2번째 값(S라고 생각하고)과 찾고자 하는 값 (이걸 D라고 둡시다.)
일단 S=D라면 보나마나 찾은 거죠.
만약 D<S라면
R=(L+R)/2-1로 둡니다.
만약 D>S라면
L=(L+R)/2+1로 둡니다.
그다음 이걸 반복하면 log N 만에 값을 찾을 수 있습니다.
예
N=10, D=4일 경우
1 2 3 4 5 6 7 8 9 10 이렇게 값이 있을 경우
(1+10)/2 = 5(내림)번째 값과 4를 비교합니다.
5번째 값은 5, 따라서 D<S입니다.
그러면 R은 4가 됩니다((1+10)/2-1)
이렇게 반복하다 보면 값을 찾을수 있습니다.
L>R인 경우는 값이 없는 경우이므로 이걸 체크하면 되겠죠.
배열이 1에서 N개가 있다면(이걸 a(i)라고 둡시다)
물론 이 배열은 오름차순으로 정렬 되어 있어야 합니다.
일단 L=1,R=N로 둡니다.
그다음 중간값인 (L+R)/2번째 값(S라고 생각하고)과 찾고자 하는 값 (이걸 D라고 둡시다.)
일단 S=D라면 보나마나 찾은 거죠.
만약 D<S라면
R=(L+R)/2-1로 둡니다.
만약 D>S라면
L=(L+R)/2+1로 둡니다.
그다음 이걸 반복하면 log N 만에 값을 찾을 수 있습니다.
예
N=10, D=4일 경우
1 2 3 4 5 6 7 8 9 10 이렇게 값이 있을 경우
(1+10)/2 = 5(내림)번째 값과 4를 비교합니다.
5번째 값은 5, 따라서 D<S입니다.
그러면 R은 4가 됩니다((1+10)/2-1)
이렇게 반복하다 보면 값을 찾을수 있습니다.
L>R인 경우는 값이 없는 경우이므로 이걸 체크하면 되겠죠.