자료구조 <이진탐색> 알고리즘 이해

이진탐색

1. 정렬시켜야 한다.

2. 순차탐색은 배열의 값을 하나하나 비교하지만 이진탐색은 아래 그림과 같이 반으로 나눠서 비교하고 나머지는 버리는 식으로 진행한다.

while(1) = 무한반복, 반복횟수(count) = 1

end=2가 되었으므로 다시 위에 코드로 넘어가서 진행한다.

searchIdx = 1이 되었고 아래 코드로 진행하면 아래 그림과 같다.

이번에는 start = 2가 되었으므로 다시 위에 코드로 가서 진행한다.

searchIdx = 2이므로 arr[searchIdx] = 5가 된다. target과 arr[searchIdx]와 같아지므로 결과값을 출력한다.

다시 한 줄씩 이해하면서 코드를 이해한다.

이 코드의 구성이 어떻게 돌아가는 지도 이해한다.

선형 탐색과 이진 탐색

선형 탐색과 이진 탐색은 trade off 관계이다.

선형 탐색은 하나하나 일일이 값을 찾는 반면에

이진 탐색은 반을 기준으로 비교를 해 찾아가는 방식으로 좀 더 효율적이다.

이직 탐색의 단점은 정렬해야 한다는 점이지만 단점 대비 장점이 더 많다.