[알고리즘] 이분탐색 이해하기

이분탐색 이라는 메뉴가 알고리즘에서 자주 사용되는 것 같아 정리를 해보려고 합니다.

이분 탐색이란?

오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘입니다..
반으로 나누는 기준은 중간값(mid) 입니다.
중간 값(mid)과 비교하여 검색값(X)을 찾습니다.
중간 값을 찾아야 하기 때문에  반드시 정렬된 배열에서만 사용할 수 있습니다.

중간 값(mid)을 선택하여 검색값(X)과 비교합니다.
검색값(X)이 중간 값(mid)보다 작으면 중간 값(mid)을 기준으로 왼쪽으로 다시 탐색, 크다면 오른쪽으로 다시 탐색합니다.

중간 값(mid) = low + (high + low) / 2  (인덱스기준)

예시로 찾고자 하는값이 41일 때, 배열의 시작 지점이 low가 되고 끝 지점이 high가 되며 이 두 값을 이용해 mid값을 구합니다.

배열의 중간 값 17은 찾고자 하는 값 41보다 작으므로 해당 중간 값부터 좌측 끝값을 제거 하고 우측부터 시작해 다시 중간 값을 선택하고 찾고자하는 값(x)를 찾습니다.

중간 값 41과 찾고자 하는 값 41과 일치하므로 값을 찾았습니다.

참조블로그

https://hstory0208.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Binary-Search%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89%EC%9D%B4%EB%9E%80

[알고리즘] Binary Search(이진 탐색/이분 탐색)이란?