[자료구조](21)[탐색 알고리즘]

내가 찾는게 존재하는가? 그렇다면 어디에?

• 자료구조에 맞는 탐색
• 시간, 메모리, 이식성 따져봐야 함
• 특수 상황에선 특정 알고리즘이 빠를수도?

 

선형 탐색 (linear search)

말 그대로 브루트 포싱
인덱스를 1씩 증가시키며 탐색

 

종료 조건

• 찾았는가?
• 맨 끝인가?

사용처

• 소규모의 데이터셋
• 한번만 탐색하고 끝인 경우

최선	평균	최악
O(1)	O(N/2), 즉, O(N)	O(N)

 

예) 1, 3, 4, 2, 5 에서 2를 찾아라
    1->3->4->2 탐색 종료
예) 1, 3, 4, 5, 6 에서 2를 찾아라
     1->3->4->5->6
     끝에 도달한지 검사 -> 종료

 

보초 선형 탐색 (sentinel linear search)

찾고자 하는 값을 맨 뒤에 넣어 선형탐색의 종료 조건 중
맨 끝인가? 를 검사 안해도 됨 <- 근데 큰 차이는 없다...
    특히 linked list에서 많이 사용됨

 

사용처 (일반 선형 탐색이랑 똑같음)

• 소규모의 데이터셋
• 한번만 탐색하고 끝인 경우

최선	평균	최악
O(1)	O(N)	O(N)

 

예) 1, 3, 4, 5, 6 에서 2를 찾아라
     맨 뒤에 보초값으로 2를 집어넣음
     1, 3, 4, 5, 6, 2
     1->3->4->5->6->2 탐색 종료

 

이진 탐색 (binary search)

"정렬된 데이터"에서만 작동
매 탐색마다 2분할로 나눠 탐색

 

사용처

• 정렬된 데이터에서 빠른 탐색을 원할 때 사용!

주의 사항

• int형 오버플로우
  int mid = (low+high)/2 <- low, high가 클 때는 오버플로우의 위험
  int mid = low + (high - low)/2 로 구현하자
• off-by-one 오류
  인덱스가 1만큼 차이나서 오류 발생
      1개 검사 안하고 넘어가기
      무한루프
      배열 크기 이상 참조 등...

최선	평균	최악
O(1)	O(logN)	O(logN)

 

예) 1, 2, 3, 4, 5, 6, 7 에서 3를 찾아라
     중간값인 5를 기준으로 3 < 4 이므로 왼쪽 탐색
     1, 2, 3
     중간값인 2를 기준으로 3 > 2 이므로 오른쪽 탐색
     3 <- 종료

 

해시 탐색 (hash search)

해시테이블을 이용해 탐색

단점

• 추가 메모리 필요: bucket 잡아야 함
• 충돌 처리도 구현해야 함

사용처

• Look Up table
• 사전형 구조

최선	평균	최악
O(1)	O(1)	O(N)

 

점프 탐색 (jump search)

"정렬된 데이터"에서만 작동
인덱스를 root(N)씩 증가시키며 탐색
     만약 점프한 인덱스의 값이 타겟보다 크면
     반대로 돌아 선형 탐색

사용처

• 정렬된 데이터
• 이식성이 필요할 때 (이진탐색보다 단순함)

최선	평균	최악
O(1)	O(root(N))	O(root(N))

 

예) 1, 2, 3, 4, 5, 6, 7, 8, 9 에서 5을 찾아라
     root(9) = 3 씩 건너뛰며 탐색
     1 -> 4 -> 7
     5<7이므로 반대로 돌아 탐색
     7->6->5 종료

 

보간 탐색 (interploation search)

"균등 분포"를 가진 "정렬된 데이터"에서만 작동
     즉, value와 index가 비례관계
이진탐색이지만, 더 효율적
중간 값의 인덱스를 직접 연산한다
     pos = low + {(key - arr[low])(high - low)} / (arr[high] - arr[low])
     즉, pos를 high, low로 기울기를 계산하고 (arr[low], low)를 지나는 직선에 key를 넣은 것이다.
     (주의! 우리가 계산하고 싶은 pos는 index이다. 따라서 index를 y축으로 둬야 함

     이후 이진탐색처럼
     만약 arr[pos] == key: 종료
     만약 arr[pos] < key: low = pos + 1
     만약 arr[pos] > key: high = pos - 1

 

사용처

• 균등분포를 가진 정렬된 데이터
• 이진탐색보다 더 빠른거 원할 때

최선	평균	최악
O(1)	O(log(logN))	O(log(logN))

 

예) 1, 2, 3, 4, 5, 6, 7, 8, 9 에서 5을 찾아라
     y = x+1 이다. 그리고 여기에 5를 넣는다면
     6 즉, 5는 인덱스 6에 있다.

 

지수 탐색 (exponential search)

이진탐색이지만, 배열의 크기가 정해지지 않을 때 더 효울적
"정렬된 데이터"에서만 작동
탐색 범위를 지수적으로 2배씩 증가시키며 탐색
     arr[i] >= target이 될 때까지 탐색 범위 증가
     해당 탐색 범위 내에서 이진탐색으로 데이터 찾기

 

사용처

• data stream
• 무한 리스트
• 크기 모르는 배열
• 찾고자 하는게 비교적 앞에 있을 때

최선	평균	최악
O(1)	O(logI)	O(logI)

I = target의 index

 

예) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 에서 8을 찾아라
     arr[0]과 비교 1<8
     arr[1]과 비교 2<8
     arr[2]과 비교 3<8
     arr[4]과 비교 5<8
     arr[8]과 비교 9>8
     arr[4]부터 arr[8]까지 이진탐색

 

삼분 탐색 (ternary search)

"극점"이 하나 존재하고(unimodal function), "정렬된 데이터"에서만 작동
3개의 구역으로 나눠 탐색한다
     low, high 구간을 길이로 3개로 나눔
     만약 func(mid1) < func(mid2) : high = mid2-1
     만약 func(mid1) > func(mid2) : low = mid1+1
     만약 func(mid1) == func(mid2) : mid1, mid2 사이 좁히기
     low == high일 때 까지 반복

 

사용처

• 최적화
• 미분

최선	평균	최악
O(1)	O(logN)	O(logN)