반응형



[ 이 게시물은 개념 설명 게시물이고 소스코드는 다음 게시물에 있습니다. ]


** 순차 탐색 알고리즘 보단 훨씬 좋은 성능을 보이지만, 배열이 정렬되어 있어야 한다는 제약이 따른다.


어떤 배열에서 3을 찾고 싶을때,


이진 탐색 알고리즘의 첫 번째 시도:


1. 배열 인덱스의 시작과 끝은 각각 0과 8이어야한다.


2. 0과 8을 합하여 그 결과를 2로 나눈다.( (0 + 8) / 2 = 4 )


3. 2로 나눠서 얻을 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인하고, arr[4]의 값을 본 후 오른쪽을 탐색해야될지, 왼쪽을 탐색해야될지 정한다.



** 9개에서 4개로 탐색 대상이 줄어들었는 것을 확인할 수 있다.



이진 탐색 알고리즘의 두 번째 시도:


1. 0과 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다. (0+3)/2 = 1.5 = 1


2. arr[1]에 저장된 값이 3인지 확인 한 후, 왼쪽,오른쪽 탐색을 결정한다.(첫 번째 시도와 동일)



** 이진 탐색은 탐색이 이루어 질 때 마다 탐색 대상이 1/2씩 줄어드는 장점이 있다.


이진 탐색 알고리즘의 세 번째 시도:


1. arr[2]와 arr[3]이 남았으니, (2+3)/2 = 2.5 = 2를 한 후 arr[2]의 값이 3인지 확인한다.


2. 3이 아니면 왼쪽, 오른쪽 탐색을 결정하면  arr[3]뿐이니 arr[3]의 값이 3임을 확인할 수 있다.







반응형