Searching problem (linear, binary)

1. linear search

 

리스트 처음부터 끝까지 하나씩 비교해가며 찾는 방법

Time complexity 는 O(N)

def LinearSearch(list, value):
	for i in range (len(list)):
    	if list[i] == value:
        	return i
    return -1

 

2. Binary search (리스트가 정렬 되어있다는 전제에서 search)

 

리스트 중간 value 와 비교하여 리스트의 절반에서 탐색하는 방법

Time complexity 는 O(log N)

def BinarySearch(list, value):
	first = 0
    last = len(list) - 1
    
    while first <= last :
    	mid = (first + last) // 2
        if list [mid] == value:
        	return mid
        elif list [mid] < value:
        	first = mid + 1
        else: 
        	last = mid - 1
    return -1