Sequential Search (순차 탐색)

: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

• 데이터의 정렬 여부와 상관없이 가장 앞에 있는 원소부텉 하나씩 확인

Code

def sequencial(data_list, search_data):
    for index in range(len(data_list)):
        if data_list[index] == search_data:
            return index
    return -1

Analysis

• 최악의 경우 리스트 길이가 N일 때 N번 비교해야 함
  시간 복잡도 = $O(N)$
  

---

Binary Search (이진 탐색)

Idea

• 데이터가 정렬되어있을 때 사용
• 탐색할 자료를 둘로 나누어 해당 데이터를 탐색하는 방법

How To

• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는다

1. Divide: 리스트를 두 개의 서브 리스트로 나눈다
2. Concour:
   • 찾으려는 데이터가 중간값보다 작으면, 뒷 부분의 서브 리스트에서 데이터를 찾는다.
   • 찾으려는 데이터가 중간값보다 크면, 앞 부분의 서브 리스트에서 데이터를 찾는다.

Code

1. 재귀 함수로 구현

def binary_recur(array, target, start, end):
    
    if start > end:
        return
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간값보다 찾으려는 데이터가 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_recur(array, target, start, mid-1)
    # 중간값보다 찾으려는 데이터가 큰 경우 오른쪽 확인
    else:
        return binary_recur(array, target, mid+1, end)

2. 반복문으로 구현

def binary(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        # 중간값보다 찾으려는 데이터가 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid-1
        # 중간값보다 찾으려는 데이터가 큰 경우 오른쪽 확인
        else:
            start = mid+1
    return None

Analysis

• 시간복잡도 = $O(logN)$
  N개의 리스트를 매번 반으로 나누어 1이 될 때까지 비교연산 진행