Searching & Sorting (1)

Sequential Search

linear search라고도 하며 아주 직관적으로 0번 index부터 차근차근 search해 나가는것을 말한다. 끝까지 확인해봐야 하기 때문에 항상 O(n)만큼의 시간이 걸린다.

만약 정렬되어 있을 경우, 원하는 값이 나오거나 그 값보다 큰 값이 나오면 멈추면된다.

구현

• unordered arr일 때

def seq_search(arr, ele):
    pos = 0
    found = False
    
    while pos < len(arr) and not found:
        if arr[pos] == ele:
            found = True
        else:
            pos += 1
            
    return found

• ordered arr일때

def ordered_seq_search(arr, ele):
    pos = 0
    found = False
    stopped = False
    
    while pos < len(arr) and not found and not stopped:
            
        if arr[pos] == ele:
            found = True
        elif arr[pos] > ele:
            stopped = True
        else:
            pos += 1
    
    return found

Performance

앞서 말했듯 O(n)이라고 보는게 맞다. 다만 array가 정렬되어 있을 때와 그렇지 않을 때의 차이만 짚고 넘어가자. 만약 unordered array에서 item이 존재하지 않는 경우에는 어떠한 경우든 O(n)이 된다. 그러나 ordered array에서는 best : 1, worst : n , average : n/2이 되서 더 빠를 수 있는 것이다.

Binary Search

BinarySearch의 경우 arr를 반으로 쪼개가며 해당 item을 찾아나가는 과정이다. arr의 중앙에 있는 값과 item을 비교하여 작으면 item이 작다면 leftside, 크다면 rightside에 동일한 작업을 수행하며 찾아나간다.

구현

def rec_binary_search(arr, ele):
    
    if len(arr) == 0:
        return False
    else:
        mid = len(arr) // 2
        if arr[mid] == ele:
            return True
        elif arr[mid] < ele:
            return rec_binary_search(arr[mid+1:], ele)
        else:
            return rec_binary_search(arr[:mid], ele)

Performance

반으로 계속해서 나눠나가기 때문에 Time Complexity는 O(logn)이 된다.