[Python] 이진(이분)탐색 알고리즘

오늘 배운 내용 중 이진탐색 알고리즘에 대한 정리

 

이진탐색 알고리즘은 정렬된 상태로 이루어진 리스트에 대한 탐색임!

강사님이 일부 달아주신 주석에 추가적으로 복습하며 이해한 부분 주석처리하였음

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#이분(이진)탐색 (정렬이 되어 있는 경우 반 나눠서 탐색)   def binary_search(arr, x): #x: 찾고자 하는 값     start = 0     end = len(arr) - 1       while start <= end:         mid = (start + end) // 2  # // 정수로 나눔. 따라서  끝의 절반으로 나누면 안됨. # 25 기준으로 작으면 앞 부분  절반, 크면 뒷 부분 절반         if x == a[mid]: # 본인 이해: 예를들어 현재는 숫자 25번의 자리             return mid         elif x > arr[mid]:             start = mid + 1 # 찾고자 하는 값 x가 mid 보다 크다면 오른쪽으로 탐색         else:             end = mid - 1 # 찾고자 하는 값 x가 mid 보다 작다면 왼쪽으로 탐색       return -1 # 찾지 못했을 땐 -1 반환       d = [1, 4, 9, 16, 25, 36, 49, 64, 81] # 9개 숫자, 방번호 0부터 8. 9 나누기 2 -> 4. 따라서 4번째의 25가 mid. #25 기준으로 또 절반 나눔.  print(binary_search(d, 36)) print(binary_search(d, 50))   Colored by Color Scripter

cs

 

 

이해를 위해 아래 블로그 링크 참고하였는데, 짤로 만들어진 것 참고하면 좋을거 같다.

blog.naver.com/dnfla420/222093579890

순차 탐색과 이진(이분) 탐색 | Sequensial & Binary | Search | 파이썬 | 알고리즘

 

작성일: 2021. 4. 23. 15:58 

기존 블로그 글 이전일: 2021. 5. 7. 09:24