3. 검색 알고리즘

 

 

1. 검색 알고리즘이란?

---

검색 문제를 해결하는 어떠한 알고리즘을 의미한다. 연속 변수 또는 이산 변수를 사용하여, 일부 데이터 구조 안에 저장된 정보를 검색하거나 문제 도메인의 검색 공간에서 계산을 하기위해 사용한다.

 

검색 알고리즘은 배열검색, 연결 리스트 검색, 이진 검색 트리 검색 이 존재하나 이번 3번째 장에서는 배열 검색의 주요 알고리즘인 선형 검색, 이진 검색, 해시법에 대해 기록할 예정이다.

 

검색 알고리즘 선택시, 검색만을 중점적으로 놓고 본다면 계산 시간이 가장 짧은 검색 알고리즘을 선택하면 되지만, 데이터 추가, 삭제  등 기능을 자주 수행해야 된다면 검색 이외의 작업에 들어가는 비용을 종합 평가하여 알고리즘을 선택해야 한다. 

 

선택할 수 있는 알고리즘이 다양한 경우에는 용도, 목적, 실행 속도, 자료 구조 등 여러 사항을 고려해서 선택해야 한다.

 

 

 

 

2. 선형 검색

---

• 가장 기본적인 알고리즘
• 선형으로 늘어선 배열에서 검색하는 경우 사용
• 키값을 가진 원소를 찾을 때까지 맨앞부터 스캔
• 구현이 쉽고 정렬되지 않은 리스트에서 사용할 수 있다는 장점

def seq_search(a: Sequence, key: Any) -> int:
    for i in range(len(a)):
        if a[i] == key:
            return i
        else:
            return -1

a의 인덱스가 key 값과 같을 경우 i 을 반환하는 코드이며, 그렇게 않은 경우에는 -1 을 반환하는 코드이다.

해당 코드는 책의 내용을 구현한 것의 일부이지만, 선형 검색 알고리즘은 앞에서부터 순차적으로 비교하면서 같은 값이 나오는지를 비교하는 것이다.

 

 

 

 

 

3. 이진 검색

---

• 배열 데이터가 정렬되어 있어야 한다
• 선형 검색보다 빠르게 검색할 수 있다
• 정렬된 배열에서 좀 더 효율적으로 검색할 수 있음
• 처음 중간의 값은 임의의 값으로 선택하여 그 값과 찾고자 하는 값의 크고 작음을 비교
• 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다
• 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점

    while True:
        pc = (pl + pr) // 2 # 중앙원소의 인덱스
        if a[pc] == key:
            return pc
        elif a[pc] < key:
            pl = pc + 1
        else:
            pr = pc - 1

        if pl > pr:
            break
            return -1

처음에 인덱스의 중앙값을 구한다음에 중앙값과 비교하면서 크거나 작은 경우를 따져가면서

내가 찾고자 하는 값을 찾는 스크립트이다.

 

따로 정렬을 하는 알고리즘은 넣지 않았기 때문에 

위와같이 정렬이 되어 있어야 사용할 수 있다는 것을 알 수 있다

 

 

 

 

 

4. 해시법

---

• '데이터를 저장할 위치 = 인덱스' 를 간단한 연산으로 구현
• 검색, 추가, 삭제도 효율적 수행 가능

 

해시법에 대한 자세한 설명은 아래 링크를 참고하여 나중에 또 공부할 것

https://sung-jun.tistory.com/96

알고리즘 - 해시법(1)