📌 선형검색 (Linear Search)

데이터 분석이나 엔지니어링을 하다 보면 데이터 속에서 특정 값을 빠르게 찾는 일이 자주 필요.
예를 들어, 로그 데이터에서 특정 사용자 ID를 찾거나, CSV에서 특정 열 값이 있는 행을 찾는 경우가 그렇다.
이때 가장 단순하게 적용할 수 있는 방법이 바로 선형검색(linear search)

---

1. 선형검색이란?

• 리스트나 배열에 저장된 데이터를 앞에서부터 하나씩 차례대로 스캔하며 원하는 값을 찾는 알고리즘.
• 인덱스 0부터 끝까지 순서대로 확인.
• 시간 복잡도: O(n) → 데이터 크기에 비례해 검색 시간이 늘어남.

탐색 결과

• 검색 성공: 원하는 값을 찾은 경우
• 검색 실패: 끝까지 확인했지만 값이 없는 경우

데이터: 3  2  5  7  9  1  0  8  6  4
인덱스: [0][1][2][3][4][5][6][7][8][9]

• 7을 찾을 경우: 인덱스 0 → 1 → 2 → 3 에서 성공

---

2. 보초법 (Sentinel Method)

• 선형검색을 더 간단하게 더 효율적으로 구현하기 위한 방법
• 찾고자 하는 값을 리스트의 마지막 인덱스에 임시로 추가
• 그러면 탐색할 때 매번 i < len(nums) 같은 경계 조건을 검사하지 않아도 됨.

데이터: 3 2 5 7 9 1 0 8 6 4 9
인덱스: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

• 찾는 값 = 9
• 검색 성공: 마지막 인덱스 이전에서 9가 발견된 경우
• 검색 실패: 마지막 인덱스(보초)에서만 9가 발견된 경우

---

3. 정리

• 선형검색: 단순하고 직관적인 탐색 방식 (O(n))
• 보초법: 마지막에 값을 추가해 경계검사없이 탐색 가능
• 실무 포인트:
  • 작은 데이터 → 선형검색으로 충분.
  • 대규모 데이터 → 이진검색, 해시, 인덱스 같은 고급 기법 필요.

4. 실습

문제 1: 리스트에서 가장 앞에 있는 숫자 7 찾기

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

target = 7
searchResultIdx = -1  # 기본값: 못 찾았을 때 -1

for i, x in enumerate(nums):
    if x == target:
        searchResultIdx = i
        break

print("리스트:", nums)
print("리스트 길이:", len(nums))
print("찾은 인덱스:", searchResultIdx)
print("검색 결과:", f"{target} 값은 {searchResultIdx}번 인덱스에 있음." if searchResultIdx != -1 else "값이 리스트에 없음.")

리스트: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
리스트 길이: 11
찾은 인덱스: 1
검색 결과: 7 값은 1번 인덱스에 있음.

문제 2: 리스트에서 숫자 7을 모두 찾기

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

target = 7
positions = [i for i,x in enumerate(nums) if x == target]

print("리스트:", nums)
print("리스트 길이:", len(nums))
print("찾은 인덱스들:", positions)
print("검색 개수:", len(positions))

리스트: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
리스트 길이: 11
찾은 인덱스들: [1, 5, 8]
검색 개수: 3

---

📌 이진검색 (Binary Search)

1. 이진검색이란?

• 정렬된 자료구조에서 데이터를 찾는 알고리즘
• 중앙값과 비교하여 크다/작다 여부로 탐색 범위를 절반씩 줄여나감
• 시간복잡도는 O(log n) 으로, 선형검색(O(n))보다 훨씬 효율적이다.
• 대용량 데이터에서 탐색 속도가 빠르다.
  -> 10억개 데이터도 30번 이내 비교로 탐색 가능

2. 동작원리

1. 데이터가 정렬되어 있어야함
   -> 그만큼 새로운 데이터 삽입/삭제가 잦으면 정렬 유지 비용이 큼. -> 정적 데이터(변경 적음) 탐색에 적합.
2. 리스트의 중앙값을 선택한다.
3. 찾는 값(target)과 비교한다.
   • target == mid → 탐색 성공
   • target < mid → 중앙값보다 왼쪽 범위만 탐색
   • target > mid → 중앙값보다 오른쪽 범위만 탐색
4. 탐색 범위를 절반으로 줄여가며 반복한다.

데이터: 1 2 3 4 5 6 7 8 9
인덱스: [0][1][2][3][4][5][6][7][8]

-> 찾는 값: 2
1. 중앙값 = 5 → 2 < 5 → 왼쪽 구간 [1, 2, 3, 4, 5]
2. 새로운 중앙값 = 3 → 2 < 3 → 왼쪽 구간 [1, 2, 3]
3. 새로운 중앙값 = 2 → target과 일치 → 탐색 성공

4. 파이썬 코드 예제

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2  # 중앙값 인덱스
        if nums[mid] == target:
            return mid  # 탐색 성공
        elif nums[mid] < target:
            left = mid + 1  # 오른쪽 범위로 이동
        else:
            right = mid - 1  # 왼쪽 범위로 이동
    
    return -1  # 탐색 실패

# --- 데모 ---
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]

print("리스트:", nums)
target = 2
idx = binary_search(nums, target)
print(f"검색 결과: {target} 값은 {idx}번 인덱스에 있음." if idx != -1 else "값이 리스트에 없음.")

리스트: [1, 2, 3, 4, 5, 6, 7, 8, 9]
검색 결과: 2 값은 1번 인덱스에 있음.

5. 활용 예시

• 이벤트 로그: 시간순 정렬된 데이터에서 특정 시점 이벤트 탐색.
• 금융 데이터: 정렬된 주가/거래 데이터에서 특정 값 찾기.
• DB 내부: 인덱스 구조(B-Tree)는 이진검색 원리를 확장 적용.

6. 실습

주어진 리스트를 오름차순으로 정렬한 뒤, 숫자 7을 이진검색을 이용해 찾고, 그 위치(인덱스)를 출력하는 프로그램을 작성.

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]

# 오름차순
print("정렬 후 리스트:", nums.sort())

# 이진검색 함수
def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2  # 중앙값 인덱스
        if nums[mid] == target:
            return mid  # 탐색 성공
        elif nums[mid] < target:
            left = mid + 1  # 오른쪽 탐색
        else:
            right = mid - 1  # 왼쪽 탐색
    return -1  # 탐색 실패
    
# 타겟 검색
target = 7
idx = binary_search(nums, target)

print("찾는 값:", target)
print("찾은 인덱스:", idx)
print("검색 결과:", f"{target} 값은 {idx}번 인덱스에 있음." if idx != -1 else "값이 리스트에 없음.")

정렬 전 리스트: [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
정렬 후 리스트: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
찾는 값: 7
찾은 인덱스: 3
검색 결과: 7 값은 3번 인덱스에 있음.