[알고리즘] 선형탐색과 이진탐색

안녕하세요

오랜만에 글을 올리네요...

한동안 게으르게 지내다보니 글을 쓰지 못했네요 ㅠ_ㅠ 

그래서 요즘 알고리즘 공부를 하고 있어요 코딩테스트 준비랄까...

공부하면서 혼자 정리겸 알고리즘 관련 포스팅을 시작하려고 합니다!!

부족한 부분이 많지만, 여러분께 도움이 되었으면 좋겠어요.

오늘은 선형탐색과 이진탐색에 대하여 정리 하려고합니다.

---

선형탐색 알고리즘이란?

영어로는 Linear Search Algorithm 이라고 합니다.

선형탐색은 여러 값들중에서 정직하게도 순서대로 처음부터 하나하나 검색하여 값을 찾는 것입니다.

코드 예시를 들어 봐보겠습니다.

코드는 파이썬으로 작성되었습니다. 찾으려는 값이 5이며, [1, 2, 3, 5, 7, 8, 9] 라는 리스트가 주어졌을때를 가정하여 

linear_search라는 함수를 작성하였습니다.

값이 있는경우 True를 반환하며, 없을경우 False를 반환합니다.

def linear_search(search_value, value_list)
    #search_value는 찾고싶은 값을 전달 받습니다.
    
    # for 반복문을 이용하여 value_list의 처음부터 끝까지 진행합니다.
    for val in value_list:
        # 각 요소와 찾으려는 search_value값을 비교하는 if문을 작성합니다.
        # 값을 찾은경우 검색을 종료하고 True를 리턴합니다.
        if val == value_list:
            return True 
 
    # 반복문이 끝날때까지 찾지 못한다면 False를 리턴합니다.
    return False
 
 
 
print(linear_search(5, [1, 2, 3, 5, 7, 8, 9,]))

이렇듯 많이들 사용하실꺼에요. 기본적으로 while문이나 for문을 이용하여 값을 비교하는 경우가 많으시니까 쉽게 이해 가능하실꺼에요.

다음으로는 이진탐색 알고리즘입니다.

---

이진탐색 알고리즘이란?

영어로는 Binary Search Algorithm 이라고 합니다.

이진탐색은 정렬된 리스트를 반씩 나누어 검색하여 값을 찾는 것입니다.

코드 예시를 들어 봐보겠습니다.

위와 마찬가지로 찾으려는 값이 5이며, [1, 2, 3, 5, 7, 8, 9] 라는 리스트가 주어졌을때를 가정하여 진행하도록 하겠습니다.

def binary_search(search_value, value_list)
    # search_value는 찾고싶은 값을 전달 받습니다.
    
    start_index = 0                        # 시작지점을 선언합니다.
    end_index = len(value_list) - 1        # 종료지점을 선언합니다.
    
    
    while start_index <= end_index:
        mid_index = (start_index + end_index) // 2    # 중간지점을 선언합니다.
        
        if value_list[mid_index] > search_value:            # 중간지점의 값이 찾으려는 값보다 큰경우 
            end_index = mid_index - 1                        # 종료index에 중간index를 대입합니다.
        elif value_list[mid_index] < search_value:            # 중간지점의 값이 찾으려는 값보다 작은경우
            start_index = mid_index + 1                        # 시작index에 중간index를 대입합니다.
        else:                                                # 만약 값을 찾는다면 True를 반환합니다.
            return True
    # 반복문에서 값을 반환하지 않으면 value_list내에 찾으려는 값이 없기 때문에 False를 반환합니다. 
    return False                            
        
 
 
 
print(linear_search(5, [1, 2, 3, 5, 7, 8, 9,]))

이렇게 값을 반으로 줄이면서 찾는것이 이진탐색입니다.

그렇다면 어떤 경우에 선형탐색 알고리즘을 사용하고, 어떤 경우에 이진탐색 알고리즘을 사용할까요?

---

선형탐색 VS 이진탐색

각각의 알고리즘에서 가장 빨리 찾는 경우와 최악의 경우를 비교해보도록합시다.

다음와 같이 [1, 2, 3, 4, 5, 6, 7, 8] 길이가  8인 리스트가 주어졌다고 가정해봅시다.

1. 선형탐색

  - 가장 빨리 찾는 경우: 1번 ( 찾으려는 값이 1일 경우 )

  - 최악의 경우: 8번 (찾으려는 값이 8일 경우)

2. 이진탐색

 - 가장 빨리 찾는 경우: 1번 ( 찾으려는 값이 4일 경우 )

 - 최악의 경우: 3번 (찾으려는 값이 1일 경우)

이렇게 비교해보면 이진탐색이 더 빠르게 값을 찾을 수 있다는것을 알 수 있습니다.

찾아야할 리스트의 길이가 크지 않다면 차이가 적을 수 있으나, 길이가 점점 길어 질수록 그 차이는 더 많이 벌어지게 됩니다.

주의사항!

단, 이진탐색의 경우 정렬된 리스트일때만 사용이 가능합니다.

이렇게 오늘은 탐색 알고리즘의 2가지를 공부해 보았는데요. 이해가 가시련지요??

항상 어떤 것이 좋다라고는 할 수 없기 때문에 상황에 따라 그때그때 어떤게 최선일지 생각하며 프로그래밍을 하시는 여러분이 되면 좋겠습니다.

감사합니다!