[CS] 기본검색 알고리즘(Basic Search Algorithm)

기본검색 알고리즘(Basic Search Algorithm)

 

1. 탐색

저장된 정보들 중에서 원하는 값을 찾는 것

프로그래밍에서 가장 간단하고 대표적인 문제가 탐색 문제

 

2. 탐색 알고리즘의 종류

• 선형 탐색 알고리즘 (linear search algorithm)
  • 왼쪽부터 순서대로 확인
  • 찾고자 하는 값을 리스트의 맨 앞에서부터 끝까지 차례대로 찾아 나가는 방식
    (왼쪽부터 순서대로 확인)
  • 장단점
    • 장점 : 검색 방법 중 가장 단순하여 구현이 쉽고, 정렬되지 않은 리스트에서도 사용 가능
    • 단점 : 검색할 리스트의 길이가 길면 비효율적
• 이진 탐색 알고리즘 (binary search algorithm)
  • 중간지점을 기준으로 반씩 제외하는 방식
  • 오름차순으로 정렬되어 있는 리스트에서 특정한 값을 찾을 때, 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식
  • 장단점
    • 장점 : 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠름
    • 단점 : 정렬된 리스트에만 사용 가능

 

3. 선형탐색의 쓰임

• 이진 탐색의 전제 조건 : 정렬된 리스트 - 이진탐색
• 만약, 리스트가 정렬되지 않은 상태 : 정렬 x 리스트 - 선형탐색

# 선형 탐색 알고리즘 for 정렬안된 리스트
def linear_search( element, some_list ):
    # list 탐색을 idx를 가지고 할 수 있는 range(len()=1부터 개수) = 0부터 인덱스
    for i in range(len(some_list)):
        if some_list[i] == element:
            return i
    return None


# 이진 탐색 알고리즘 for 정렬 리스트
def binary_search(element, some_list):
    # 1. 매번 중간인덱스로 가야한다 -> 처음과 끝 인덱스를 변수로 관리하여, a+b/2를 이용하자
    # 2. 초기값
    start_index = 0
    end_index = len(some_list) - 1 # 3. 어떤 리스트의 마지막인덱스는 len()=개수 - 1

    # 7. 최악의 경우의 수만큼 :  for _ in ...   2^m = len(list) 의 m만큼.. -> log2( len(list))
    # 8. 그냥 반씩 줄이다가, 남은 원소가 1개가 되었을 때까지를 조건으로
    #   조건동안 유지할 반복문  : while
    #   - 만약, list에 [2]만 남았는데, 찾고자하는 element가 1이다.
    #   - start, end, mid_index = 0 =>   some_list[0] = 2 > element   =>  
    #   - element가 왼쪽에 있다고 판단하여, end_index = mid -1 = 0 -1을 대입하게된다.
    #   - 리스트가 1개일 때는, 원하는 것이 없을 때 엇갈리게 된다.
    #   - 나는 리스트 1개, 원하는 것이 항상 그것이라고만 생각하는 경향이 있음.
    while start_index <= end_index:
        # 4.  반복분에서 변하는 값
        mid_index = (start_index + end_index) // 2 # 5. 홀짝관계없이 그냥 정수몫(나중에 -1, +1 알아서됨)

        # 6.
        if element == some_list[mid_index]:
            return mid_index

        elif element < some_list[mid_index]:
            end_index = mid_index - 1
            #다시 반복
        else:
            start_index = mid_index + 1
            #다시반복
    # 9.
    return None

 

[참고자료]

https://nittaku.tistory.com/487

탐색 알고리즘 - 1. 선형 탐색 / 2. 이진 탐색 알고리즘