검색
검색(Search)이란 아이템의 집합 중에서 특정 속성을 가진 한 아이템을 찾는 과정
검색을 하는 이유?
많은 정보를 효율적으로 얻어내기 위해서 알고리즘이 필요
검색 과정을 향상시키기 위해 데이터를 정리하는 방법들이 있습니다.
데이터를 특정한 순서로 저장하면 필요한 항목을 찾기가 쉬워집니다.
Unordered Linear Search
배열의 항목들이 정렬되지 않은 경우, 특정 항목을 검색하려면 전체 배열을 스캔해서 그 항목이 주어진 리스트 안에 있는지 여부를 확인
Sorted/Ordered Linear Search
배열의 항목들이 정렬되어 있는 경우, 전체 배열을 스캔해서 그 항목이 주어진 리스트 안에 있는지 여부를 확인할 필요가 없습니다.
Binary Search
찾으려는 타겟이 선택한 곳보다 작은지 큰지를 확인하여 절반씩 탐색을 반복합니다.
def binarySearch(start, end, target):
if start > end:
return
mid = (start+end)//2
if numbers[mid] == target:
print(mid+1,"번")
elif numbers[mid] > target:
return binarySearch(start, mid-1, target)
else:
return binarySearch(mid+1, end, target)