[알고리즘] 이진 탐색 (Binary Search)

❓이진 탐색 (또는 이분 탐색, Binary Search) 란?

 

정렬되어 있는 (이진 탐색의 주요 조건) 배열에서 데이터를 찾으려 시도할 때,

순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라

탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법이다.

 

이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만,

검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다.

 

 

 

 

👉동작 방식

이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾는다.

중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있다.

 

이진 탐색의 동작 방식은 다음과 같다.

 

1. 배열의 중간 값을 가져온다.

 

 

2. 중간 값과 검색 값을 비교한다.

 

     1. 중간 값이 검색 값과 같다면 종료한다. (mid = key)

 

     2. 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다.

         (mid < key)

 

     3. 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색한다.

         (mid > key)

 

 

3. 값을 찾거나 간격이 비어있을 때까지 반복한다.

 

 

 

 

💻이진 탐색 사용하기

이진 탐색을 사용하여 key = 32 값을 찾는 과정을 보도록 하자.

 

1. 먼저, 배열의 가운데를 결정한다.

mid = low + (high - low) / 2
    = 0 + (9-0) / 2
    = 4

 

 

2. 중앙 값과 검색 값을  비교한다.

A[4] < key 이므로 배열의 오른쪽 구간을 검색 범위로 정한다.

low = mid + 1
    = 4 + 1
    = 5

 

 

3. 중앙 값을 결정한다.

mid = 5 + (9-5) / 2
    = 7

 

 

4. 중앙 값과 검색 값을 비교한다.

A[7] > key 이므로 배열의 왼쪽 구간을 탐색 범위로 정한다.

high = mid - 1
     = 7 - 1
     = 6

 

 

5. 중앙 값을 결정한다.

mid = 5 + (6-5) / 2
    = 5

 

 

6. 중앙 값과 검색 값을 비교한다.

A[5] = key 이므로 탐색을 종료한다.

 

 

 

 

🔍종료 조건

이진 탐색의 종료 조건은 두 가지가 있다. 다음 조건 중 하나라도 성립하면 검색을 종료한다.

 

1. 검색을 성공할 경우

• 리스트에서 검색할 값과 같은 요소를 발견한 경우
• a [mid] == key

 

2. 검색을 실패한 경우

• 더 이상 검색할 범위가 없을 경우
• low > high

 

 

 

 

💡구현

위 종료 조건을 가지고 구현을 해보겠다.

이진 탐색은 두 가지 구현 방법이 존재한다.

 

1. 반복문을 이용한 방법

 

 

2. 재귀 함수를 이용한 방법

 

---

참고

• https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search
• https://yoongrammer.tistory.com/75

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

이진 탐색 (Binary search) 개념 및 구현