파이썬 이진 검색 binary search

정렬되어 있는 데이터가 있을 때, 그 중에서 내가 찾는 값이 몇번째에 있는지(=인덱스) 쉽게 알아내는 방법이 이진 검색이다. 데이터를 절반으로 나누어서 찾는 값이 절반 왼쪽에 있는지, 오른쪽에 있는지, 아니면 그 절반 지점이 찾는 값인지 확인하는 작업을 계속 반복한다.

다음의 순서로 설명한다. 그림으로 설명 코드로 설명 [심화] 재귀함수로 구현 < 작가 FoodieFactor, 출처 pixabay.com > 그림으로 설명 [1, 2, 3, 4, 5, 6, 7]로 된 리스트에서 5를 찾는 경우를 그림으로 설명한다.

코드 읽기에 자신이 있는 분은 '코드로 설명'을 바로 읽으셔도 된다. 코드로 설명 먼저 리스트의 첫번째 요소의 인덱스값(0)을 'low'라는 변수에 넣고, 리스트의 마지막 요소의 인덱스값( len(list) - 1)을 'high'라는 변수에 넣는다. low = 0 high = len(list)-1 다음 low값과 high값의 절반 지점이 되는 중앙값 middle을 구한다 (...