🧬 이분 / 이진 탐색 알고리즘 쉽게 설명 (그림+)

 

🧬 이진 탐색 알고리즘 

이진 탐색은 정렬된 배열에서 특정 값을 찾는 데에 사용되는 검색 알고리즘입니다.

이진 탐색의 핵심은 배열이 정렬되어 있다는 것입니다. 배열이 정렬되어 있기 때문에, 배열을 반씩 나누어서 탐색 범위를 줄일 수 있습니다.

 

이진 탐색은 배열의 중간 값(mid)을 선택하고, 찾으려는 값이 중간 값보다 작으면 배열의 왼쪽 반쪽을, 찾으려는 값이 중간 값보다 크면 배열의 오른쪽 반쪽을 탐색합니다.

 

이러한 과정을 반복하여 원하는 값이 나올 때까지 탐색합니다.

이진 탐색은 탐색 범위를 반으로 나누기 때문에, 최악의 경우에도 탐색 시간이 O(log n)으로 매우 빠릅니다. 이진 탐색을 사용하여 정렬된 배열에서 값을 찾을 때, 선형 탐색을 사용하는 것보다 훨씬 효율적입니다.

 

 

아래 그림은 이진 탐색 알고리즘의 동작을 보여줍니다.

---

여기에 크기는 정렬된 1~30 배열 그리고 찾으려는 값은 22라고 가정합니다.

Try 1

 위 그림에서 찾으려는 target 값은 22입니다. 먼저, 배열의 중간 값인 15와 비교합니다.

중간값 = int((start + end) / 2) // 버림값

 

target > mid

(22 > 15)

 

start 변수를 mid값보다 +1을 해줍니다. -> start = mid+1 

 

이 부분은 버림

다시 시작!

---

 

 

Try 2

 

target < mid

(22 > 23)

 

end 변수를 mid값보다 -1을 해줍니다. -> end = mid-1 

 

---

 

 

Try 3

target > mid

(22 > 19)

 

start 변수를 mid값보다 +1을 해줍니다. -> end = mid+1 

---

 

 

Try 4

 

Try 5

mid는 내림값 입니다.

이러한 방식으로 이진 탐색은 정렬된 배열에서 값을 찾을 때 매우 유용합니다.

 

그러나 배열이 정렬되어 있지 않으면 이진 탐색을 사용할 수 없으므로 보통 해쉬함수를 사용합니다.

 

시간복잡도를 생각해서 sort함수를 사용하여 이진 탐색을 하여 효율이 좋다면 이진탐색이 사용하고 유동적으로 사용하면 됩니다.!