선형탐색과 이진탐색

선형 탐색

선형 탐색이란 원하는 값을 찾기 위해 왼쪽부터 오른쪽까지 한 번에 한 셀씩 확인하는 방법이다

배열 [1,4,5,2,6]이 있다고 하고 2를 찾는다고 하자

---

1- 1을 확인하고 2가 아니라 넘어감

2- 4를 확인하고 … 2가 아니라 넘어감

.

.

.

2가 나오면 검색 종료!

---

이 방법이 선형 검색이다 만약 N개의 원소가 있으면 빅오 표현법으로 선형 탐색은 O(N)이 걸린다( 맨앞에 있으면 한번에 찾을 수 있지만 빅 오 표현법은 최악을 표기)

 

선형 탐색 파이썬 코드

// 2를 찾는 선형 탐색
a = [1,4,5,2,6,3,7,8,9,10]

for i in a:
    if i == 2:
        print("2를 찾았습니다")
        break
    print(i)
//1
//4
//5
//2를 찾았습니다

4단계만에 찾는다

 

 

이진 탐색

이진 탐색은 업다운 게임과 비슷하다 업다운 게임은 한명이 숫자를 생각하고 그 숫자를 다른 사람이 맞추는 게임이다 1~100이 있으면 보통은 50을 고른다 그러면 “더 커” 또는 “더 작아”로 알려주게되고 정답이 있는 범위를 절반으로 줄일 수 있다

업 다운 게임

이 방식을 이용한 검색이 이진탐색이다

이진 탐색을 이용하면 선형 탐색보다 훨씬더 빠르게 탐색을 할 수 있다

하지만 이진 탐색은 정렬된 배열에서만 사용 가능하다

 

이진 탐색 파이썬 코드

a = [1,2,3,4,5,6,7,8,9,10]
goal = 7
low = 0
high = len(a)-1
i = 1

while high >= low:
    mid = (low + high)//2
    
    print(i,"번째","범위",a[low],"~",a[high])
    i += 1
    
    if goal < a[mid]:
        high = mid - 1
        
    elif a[mid] == goal:
        break
        
    elif goal > a[mid]:
        low = mid + 1

print(a[mid],"==",goal)

//1 번째 범위 1 ~ 10
//2 번째 범위 6 ~ 10
//3 번째 범위 6 ~ 7
//4 번째 범위 7 ~ 7
//7 == 7

만약 이 배열을 선형 탐색 했으면 총 7 번의 단계가 필요하지만 이진 검색에서는 4 단계만에 찾아냈다

 

 

효율성

작은 크기의 배열이면 두 탐색의 효율성 차이는 크지 않다 하지만 배열이 커지면 최대 단계수는 크게 달라진다

100개의 값을 갖는 배열

- 선형 탐색 최대 100단계

- 이진 탐색 최대 7단계

배열의 크기에 따라 효율성이 크게 나타난다 그리고 이진 탐색에서 데이터 값이 2배 증가 할때마다 1단계가 증가한다

크기가 6인 배열은 3단계이고 12인 배열은 4단계 24인 배열은 5단계 이렇게 증가한다

선형 탐색 O(n)   이진 탐색 O(log N)

 

항상 이진 탐색이 좋은것은 아니다 먼저 배열이 정렬되어 있어야한다는 조건이 있기 때문에 추가와 삭제가 느리다 선형 탐색은 정렬된 배열이 아니어도 돼서 추가와 삭제가 빠르고 검색이 느리다

	검색	추가 제거
선형탐색	느림	빠름
이진탐색	빠름	느림