[알고리즘] 이진 탐색 기법

안녕하세요? 주니하랑 입니다.

오늘은 알고리즘의 이진 탐색에 대해서 공부하는 시간인 것이에요.

코테를 유능한 개발자가 되기 위해 열심히 공부 해 보겠습니다!

소스 코드에 대해서 확인 하고 싶으신 분들께서는 주니하랑의 Git hub에 관심을 주세요!

 

---

 

 

📌 Binary Search (이진 탐색) 란?

---

 

탐색할 자료의 틀 혹은 List 등을 둘로 나누어 해당 Data가 있을 만한 곳을 탐색하는 기법인 것이에요.

쉽게 말해 내가 찾을 값을 찾기 위해 계속 두 개로 쪼개서 필요 없는 부분은 버리고를 반복하는 방법인 것이에요!

 

반응형

출처 : 패스트 캠퍼스 - 알고리즘 기술면접 완전 정복

 

위의 문제는 이진 탐색을 사용하여 처리하는 것이 가장 빠르다고 합니다.

단! 여기서 중요한 것은 정렬이 되어 있어야 한다는 점이에요!

 

  📍이진 탐색의 이해 (순차 탐색과 비교하며 이해하기)

 

출처 : 패스트 캠퍼스 - 알고리즘 기술면접 완전 정복

 

 

 

  📍분할 정복 알고리즘과 이진 탐색

 

1. 분할 정복 알고리즘(Divide and Conquer)
   • Divide: 문제를 하나 또는 둘 이상으로 나눈다.
   • Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결, 아니면 다시 나눈다.
2. 이진 탐색(Binary Search)
   • Divide : List를 두 개의 Sub List로 나눈다.
   • Conquer :
     • 검색할 숫자(search)가 List의 중간값 보다 크다면 뒷 부분의 Sub List에서 검색할 숫자를 찾는다.
     • 검색할 숫자(search)가 List의 중간값 보다 작다면 앞 부분의 Sub List에서 검색할 숫자를 찾는다.
3. 코드에 대한 생각
   • 이진 탐색은 Data가 정렬되 있는 상태에서 진행
   • Data가 [2, 3, 8, 12 ,20] 일 때,
     • binary_search(data_list, search_num) 함수를 만든다.
       • find_data는 찾는 숫자에 대한 변수
       • data_list는 Data를 담은 List
       • data_list의 중간값을 find_data와 비교한다.
         • 만약 find_data가 Data_list보다 작다면
           • 맨 앞 쪽부터 data_list의 중간까지 다시 find_data를 찾는다.
         • data_list의 중간값이 find_data보다 크다면
           • data_list 중간부터 맨 끝까지 다시 find_data를 찾는다.
         • 둘 다 아니라면, data_list의 중간값은 find_data인 경우밖에 없으므로, return으로 data_list 중간에 해당 값 위치

 

 

 

 

  📍알고리즘 분석

이진 탐색은 n개의 List를 매번 2로 나누어 그 n이 결국 1이 될 때까지 계~~~~~속 비교연산을 하여 k번(회)를 진행하는 것이에요.

• n X $\frac { 1 }{ 2 }$ X $\frac { 1 }{ 2 }$ X $\frac { 1 }{ 2 }$ ... = 1
•  X $\frac { 1 }{ 2 }^k$ = 1
• n = $2^k$ = $log_2 n$ = $log_2 2^k$
• $log_2 n$ = k

Big O 표기법으로는 k + 1이 결국 최종 시간 복잡도가 되는 것이에요. (1이 되었을 때도, 비교연산을 한번 수행하게 된답니다!)

결국 O($log_2 n$ + 1)이고, 2와 1은 상수이기 때문에 삭제가 되므로, 결과적으로는 O($log n$)가 되겠습니다!

 

 

 

---

 

 

주니하랑의 글이 마음에 드셨나요? 구독과 공감! 그리고, 댓글 그리고 방명록은 주니하랑에게 많은 힘이 됩니다