이 글은 기존 Tistory 블로그에서 옮겨온 글입니다. 원문: https://jms3084.tistory.com/18
1. 이진 검색 함수
def book_search(index_array, find_name):
pos = -1
start = 0
end = len(index_array) - 1
while start <= end:
mid = (start + end) // 2
if find_name == index_array[mid][0]:
return index_array[mid][1]
elif find_name > index_array[mid][0]:
start = mid + 1
else:
end = mid - 1
return pos
위치(pos)를 처음에 -1로 설정한다.
start≤end일 경우 계속 반복하고 mid에 start와 end의 중간값을 넣어준다.
만약 찾는 데이터와 중간값이 같을 경우 반환
찾는 데이터가 더 작을경우 end = mid - 1
찾는 데이터가 더 클경우 start = mid + 1
찾는 데이터가 존재하지 않을 경우 초기 설정한 pos값 반환 = -1
퀵 정렬과 비슷한 알고리즘 → pivot을 설정하고 분할하여 찾는 검색이다.
2. 이진검색 후 물품별로 판매 개수 리스트 반환 함수
def count_product(sell_array, sell_product):
"""
sell_array: 판매된 물건 배열
sell_product: 판매된 물품 종류 배열
"""
arr = []
for i in sell_product:
count = 0
while True:
pos = binary_search(sell_array, i)
if pos == -1:
break
count+=1
del sell_array[pos]
arr.append((i, count))
return arr
pos를 처음에 0으로 설정해주고 i를 기준으로 이진검색을 진행한다 → pos가 -1이 아닐때까지 반복
-1이 아니면 pos위치에 있는 요소를 삭제하고 count를 증가. → 계속 반복시 pos값은 최종적으로 -1이 되고 루프 탈출
arr에 카운트와 물건 이름을 튜플로 묶어서 추가
퀵 정렬로 arr 배열 정렬
3. 순차 검색
검색할 집합이 정렬되어 있지 않은 경우 순차 검색을 해야한다.
데이터 개수가 n개일 경우 **시간 복잡도는 O(n)**이다.
4. 이진 검색
정렬된 데이터 집합에서만 가능하다.
전체를 반씩 잘라 내서 한쪽을 버리는 방식을 사용한다.
데이터 개수가 계속 1/2씩만 남으므로 급격히 비교할 데이터 개수가 줄어든다.
시간 복잡도가 **O(nlogn)**이다.