목록Merge sort (1)

chae._.chae

이분검색과 합병정렬

이분검색(binary search) 분할정복(Divide-and-Conquer) 문제 : 정렬된 리스트 S에 어떤 키 x가 존재하는가? 해답 : 존재하면 x의 위치, 없다면 -1을 리턴 알고리즘 S의 정가운데 원소와 x를 비교하여 같으면 해당 위치를 리턴, 없다면 1. 정가운데 원소를 기준으로 S를 두개의 리스트로 분할 2. x가 정가운데 원소보다 크면 오른쪽, 작으면 왼쪽을 재귀호출 3. 선택한 리스트에서 얻은 답을 리턴 # Binary Search (Recursive) def location(S, low, high): if (low > high): return 0 else: mid = (low + high) // 2 print(low, mid, high) if (x == S[mid]): return ..
프로그래밍 2021. 12. 21. 10:54
이전 Prev 1 Next 다음