[알고리즘] 탐색 알고리즘① - 선형 탐색(Linear), 이진 탐색(Binary)

탐색 알고리즘 (Search Algorithms)

탐색(Search)은 말 그대로 탐색을 말하는데,

여러 데이터 중에서 원하는 값을 찾는 과정을 의미한다.

 

예를 들어 연락처에서 특정 사람의 전화번호를 찾거나,

도서관에서 책 이름 검색하기, 인터넷에서 원하는 정보를 검색하는것들 모두 탐색에 해당된다.

 

❓ 탐색 알고리즘, 중요할까?

탐색 알고리즘은 데이터의 집합에서 원하는 데이터를 효율적으로 찾기 위한 알고리즘이다.

데이터의 양이 많을수록 원하는 정보를 찾는데에 많은 시간이 소요되는데

이때 탐색 알고리즘을 사용하여 데이터를 빠르게 찾아 시간을 절약할 수 있으며

시스템 성능 개선과 함께 대용량 데이터를 효율적으로 처리할 수 있는 장점이 있기 때문에 탐색 알고리즘을 사용해야 한다.

---

1. 선형 탐색 (Linear Search)

선형 탐색은 순차 탐색이라고 불리기도 하는데,

데이터의 집합 처음부터 끝까지 요소를 순차적으로 하나씩 비교해가며

원하는 값을 찾아내는 가장 간단한 탐색 알고리즘이다.

 

예를 들어 전화번호부에서 특정 번호를 찾을 때

처음부터 하나씩 쭉 읽으면서 해당 번호를 찾는 방식이라 생각하면 된다.

---

1_1) 선형 탐색의 동작 과정

1. 배열의 첫 번째 요소부터 시작한다.
2. 현재 요소가 찾으려는 값과 같은지 비교한다.
3. 같으면 해당 인덱스를 반환 후 탐색을 종료한다.
4. 다르다면 다음 요소로 이동 후 과정을 반복한다.
5. 모든 요소를 확인했는데도 원하는 값을 찾지 못했을 경우 -1 또는 None를 반환한다.

---

1_2) 선형 탐색의 장점과 단점

👍 선형 탐색의 장점

• 구현이 매우 쉽다.
• 정렬되지 않은 데이터에서도 탐색이 가능하다.
• 적은 양의 데이터에서 효율적으로 사용할 수 있다.

👎 선형 탐색의 단점

• 데이터가 많을수록 속도가 느려진다.
• 최악의 경우 모든 데이터를 확인해야한다.

---

1_3) 선형 탐색의 시간복잡도

찾으려는 값이 첫 번째 위치에 있을 경우

한 번의 비교만으로도 탐색이 끝나기 때문에 O(1)의 시간복잡도를 가질 순 있지만,

반대로 찾으려는 값이 배열의 마지막에 위치하거나 아예 존재하지 않을 경우

모든 데이터를 확인해야하기 때문에 O(n)의 시간복잡도를 가진다.

• 최선 : O(1)
• 평균 / 최악 : O(n)

❓ 언제 선형 탐색을 사용하면 좋을까?

• 데이터가 비교적 적을 때
• 정렬되지 않은 데이터에서 탐색할 때
• 데이터가 자주 변경되어 정렬 상태를 유지하기 어려운 배열일 때
• 간단한 구현이 필요할 때

---

1_4) 선형 탐색 파이썬으로 구현하기

✅ 기능1) 반복문 사용

배열의 첫번째 요소부터 마지막 요소까지 하나씩 확인하기 위해서 반복문을 사용한다.

for i in range(len(data)):

 

✅ 기능2) 현재 값과 찾을 값 비교

현재 위치의 값과 찾으려는 값이 같다면 해당 위치를 반환하고 탐색을 종료한다.

if data[i] == target:

 

💡 선형탐색 최종코드

def linear_search(data, target):
    # 리스트 처음부터 끝까지 반복
    for i in range(len(data)):

        # 현재 요소가 찾는 값과 같다면~
        if data[i] == target:
            # 해당 요소 인덱스 반환
            return i
    # 반복이 끝날때까지 못찾으면 -1 반환
    return -1

# 탐색 할 데이터
nums = [10, 20, 30, 40, 50]

print(f"값 30의 위치: {linear_search(nums, 30)}") # 2
print(f"값 50의 위치: {linear_search(nums, 50)}") # 4

실행결과 ▶

---

2. 이진 탐색 (Binary Search)

이진 탐색은 반드시 정렬된 상태의 배열에서 탐색해야하며,

해당 배열의 중간값을 기준으로 탐색 범위를 절반씩 줄여가면서 원하는 값을 찾는 알고리즘이다.

 

예를 들어 사전에서 단어를 찾을 때,

중간을 펼쳐 찾는 단어가 왼쪽에 있는지 오른쪽에 있는지 확인하며 범위를 줄여나가는 방식이라 생각하면 된다.

 

❓ 왜 정렬이 필요할까?

이진 탐색은 중간값과 목표값을 비교하며 탐색 범위를 절반으로 줄여나가는 방식이다.

 

만약 데이터가 정렬되어있지 않을 경우 찾는 값이 중간값보다 큰지 작은지 비교한다해도

어느 방향에 찾는 값이 존재하는지 판단할 수 없다.

 

그래서 이진 탐색은 정렬된 데이터에서만 사용할 수 있다.

---

2_1) 이진 탐색의 동작 과정

1. 배열의 시작 인덱스(left)와 끝 인덱스(right)를 설정한다.
2. 중간 인덱스(mid)를 계산한다.
3. 중간 요소와 찾으려는 값을 비교하여 같다면 인덱스 반환, 값보다 요소가 크면 왼쪽 탐색, 값보다 요소가 작으면 오른쪽 탐색을 진행한다.
4. 원하는 값을 찾을때까지 과정을 반복한다.

---

2_2) 이진 탐색의 장점과 단점

👍 이진 탐색의 장점

• 탐색 속도가 매우 빠르다.
• 대용량 데이터에서 효율적으로 사용할 수 있다.
• 메모리 사용량이 비교적 적다.

👎 이진 탐색의 단점

• 꼭 정렬된 데이터 배열이여야 한다.
• 수정이 자주 발생하는 정렬일경우 유지비용이 발생한다.
• 선형 탐색보다 구현하기 복잡하다.

---

2_3) 이진 탐색의 시간복잡도

데이터가 100개가 있을 경우 첫 번째 비교 후 50개, 두 번째 비교 후 25개... 의 방식으로 남게된다.

이렇게 탐색 범위가 계속 절반씩 감소하기 때문에

데이터의 개수가 많아져도 비교 횟수는 크게 증가하지는 않는다.

찾으려는 값이 처음 선택한 중간값과 일치한다면

한 번의 비교만으로 탐색이 종료되어 O(1)의 시간복잡도를 가질 수 있게 된다.

• 최선 : O(1)
• 평균 / 최악 : O(log n)

❓ 언제 이진 탐색을 사용하면 좋을까?

• 정렬된 데이터에서 탐색을 진행할 때
• 대용량 데이터에서 빠르게 탐색을 진행해야할 때
• 탐색이 자주 이뤄지고, 데이터 수정이 적을 때

---

2_4) 이진 탐색 파이썬으로 구현하기

✅ 기능1) 탐색범위 시작과 끝 지정

현재 탐색할 범위를 나타내는 변수를 생성한다.

탐색 범위의 시작과 끝을 지정한다.

left = 0
right = len(data) - 1

 

✅ 기능2) 중간 위치 계산

이진 탐색의 특성상 항상 중간값을 기준으로 비교한다.

mid = (left + right) // 2

✅ 기능3) 탐색 범위 절반으로 줄이기

비교 결과에 따라 탐색 범위를 절반으로 줄인다.

찾으려는 값이 중간값보다 크면 오른쪽 절반만 탐색하고,

작으면 왼쪽 절반만 탐색한다.

left = mid + 1

또는

right = mid - 1

 

💡 이진탐색 최종코드

def binary_search(data, target):

    # 시작 인덱스와 마지막 인덱스
    left = 0
    right = len(data) - 1

    # 탐색범위가 존재하는동안 반복진행
    while left <= right:

        # 중간 인덱스 계산
        mid = (left + right) // 2

        # 만약 중간값이 찾는값과 같다면~
        if data[mid] == target:
            # : 해당 위치 인덱스 반환
            return mid

        # 찾으려는 값이 중간값보다 크다면~
        elif data[mid] < target:
            # : 중간기준 오른쪽 탐색
            left = mid + 1

        # 찾으려는 값이 중간값보다 작다면~
        else:
            # : 중간기준 왼쪽 탐색
            right = mid - 1

    # 반복이 끝날때까지 못찾으면 -1 반환
    return -1


# 반드시 정렬된 데이터여야 함
nums = [10, 20, 30, 40, 50]


print(f"값 30의 위치: {binary_search(nums, 30)}")  # 2
print(f"값 50의 위치: {binary_search(nums, 50)}")  # 4

실행결과 ▶

---

선형 탐색과 이진 탐색의 차이

항목	선형 탐색	이진 탐색
탐색 방식	처음부터 순서대로 탐색	중간값을 기준으로 절반씩 탐색
속도	느림	빠름
정렬 필요 여부	불필요	필요
사용하기 좋은 상황	데이터가 적거나,  정렬되지 않은 경우	데이터가 많고, 정렬된 경우