이진 검색 (Binary Search)

→ Open in Slid

• 본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.
• 본 글은 '천유린 개발 블로그'를 기반으로 작성됩니다.
• 링크 : https://taesung1993.tistory.com/

---

이진검색은 자료 가운데 있는 항목을 키 값과 비교하여 더 크면 오른쪽 부분을 검색하고, 키 값이 더 작으면 왼쪽 부분을 검색하는 방법이다.

이진검색은 분할과 정복 기법을 사용하며, 항상 정렬된 순차 자료구조에서만 사용할 수 있다.

동작 순서

이진 검색의 동작 설명을 위해 밑에 간단한 문제를 푸는 과정을 거치도록 하겠다.

Q. 정렬되지 않은 순차 자료구조 [8, 9, 1, 2, 11, 19, 29]를 이진 검색을 이용해서 11을 찾으시오.

1. 먼저 배열 [8, 9, 1, 2, 11, 19, 29]를 오름차순으로 정렬하도록 한다.

2. 배열의 길이는 7이다. 7을 2로 나누면 3.5이므로 3을 가운데 값으로 받는다. 현재 배열의 인덱스 3에는 9가 저장되어 있다. 따라서 11과 9를 비교한다. 11은 9보다 크다. 그렇기 때문에 다음 검색 범위는 9의 오른쪽인 11에서 29까지다.

3. 다음 검색범위인 [11, 19, 29]를 다음과 같이 따로 잘라준다.

자른 배열 [11, 19, 29]의 길이는 3이다. 3을 2로 나누면 1.5다. 따라서 가운데 값은 1(정수 부분만 추출)이 된다. 이제 11과 인덱스 1에 저장된 19를 비교하도록 하자. 11은 19보다 작기 때문에 19의 왼쪽 부분인 11이 다음 검색범위가 된다.

4. 다음 검색 범위인 11을 따로 잘라준다.

자른 배열의 길이는 1이다. 1을 반으로 나누면 0.5다. 따라서 가운데 값은 0이된다. 이제 11과 인덱스 0에 위치한 11을 비교하도록 한다.

-> 두수는 같다. 따라서 검색을 성공으로 처리하고 이진 검색 작업은 종료된다.

* 만약 찾는 값이 12라면, 이진 검색은 다음 과정으로 넘어갈 것이다. 그런데, 다음 과정으로 넘어가면 배열의 길이는 0이된다. 길이가 0인 배열은 검색에 실패했다는 뜻이므로, 실패 처리를 하고 이진검색을 종료시키면 된다.

본 글들은 천유린 개발 블로그를 기반으로 작성됩니다.

링크 : https://taesung1993.tistory.com/