[Algorithm] 탐색 (선형탐색, 이진탐색)

김상웅·2022년 7월 1일
0

[알고리즘]

목록 보기
15/18

✅ 탐색이란?


탐색이란 원하는 값을 저장된 값에서 찾는 것을 의미합니다.

도서관에서 우리가 책을 찾을 때 "가나다.."순으로 찾을 수도 있지만, 장르별로도 찾거나, 지금 서있는 위치에서 가장 가까운 곳부터 찾을 수도 있습니다.

우리가 컴퓨터를 활용하여 특정 데이터를 찾을 때도 마찬가지입니다.

이번 포스팅에서는 선형탐색과 이진탐색, 그리고 이진탐색과 관련된 문제와 풀이 코드를 알아보겠습니다.



✅ 선형탐색


순차검색이라고도 부릅니다.

선형탐색은 우리가 찾고자 하는 값을 리스트의 맨 앞에서 끝까지 차례대로 찾는 방식입니다.

선형탐색을 통해 값을 찾을 때의 장점은 다음과 같습니다.

  • 검색 방법이 단순합니다.

  • 정렬되지 않은 리스트에서도 사용할 수 있습니다.

반면, 다음과 같은 단점이 있습니다.

  • 검색할 리스트의 길이가 길면 비효율적입니다.

인자가 10개인 리스트에서 1개의 값을 찾을 때 선형탐색을 통해 값을 찾으면, 쉽고 빠르게 값을 찾을 수 있을 것입니다.

하지만 리스트 안의 데이터의 개수가 1억개, 혹은 10억개이면 중간에 위치해있거나 가장 끝에 있는 데이터를 찾으려면 시간이 매우 오래걸릴 것입니다.

좀 더 효율적인 탐색 방법은 없을까요? (있어요 아래 👇)



✅ 이진탐색


선형탐색보다 좀 더 효율적인 탐색방법입니다.

이진탐색은 리스트가 오름차순이나 내림차순으로 정렬되어 있어야 적용할 수 있습니다.

이진탐색의 장점은 다음과 같습니다:

  • 검색이 반복될 때마다 목표값을 찾을 확률이 높아져 선형 탐색보다 속도가 빠릅니다.

반면, 이진탐색의 단점은 다음과 같습니다:

  • 정렬된 리스트에서만 사용할 수 있습니다.

이진탐색은 처음부터 순서대로 값을 찾는 것이 아니라, 리스트의 중간부터 값을 찾아나갑니다.

이미 리스트는 오름차순이나 내림차순으로 정렬되어 있을 것입니다.

그렇기 때문에 중간에 위치한 값과 찾으려는 값을 비교하여 탐색을 이어나갈 수 있습니다.

이제 문제를 통해 알아보겠습니다.



✅ 문제


오름차순으로 정렬된 숫자들을 가진 리스트 nums를, 찾으려는 값 target을 인자로 받습니다.

target이 몇번째 index인지 반환하는 프로그램을 작성해주세요.

만약 target 값과 일치하는 값이 없으면 -1을 반환해주세요.

nums 배열에 있는 요소는 서로 중복된 값이 없습니다.
예시)

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1


📌 풀이


선형탐색으로 풀기

선형탐색으로 풀이한 코드는 다음과 같습니다.

def asnwer(nums, target):
	
    result = -1
    
    for i in range(len(nums)):
    	if nums[i] == target :
        	result = i
            return result
	
    return result

코드가 간결하고 읽기도 쉬운 것 같습니다.

만약 nums의 길이가 10억이라면,,, 어떨까요?

이번에는 이진탐색으로 풀어보겠습니다.


이진탐색으로 풀기

#1 시작과 마지막 index 값을 변수에 할당합니다.

#2 일치하지 않을 때 반환할 -1을 기본 결과 값으로 지정합니다.

#3 이진탐색을 통해 시작하는 값이 마지막 index 값을 넘지 않을 때까지 반복합니다.

#4 이진탐색은 리스트의 중간값부터 접근합니다. nums 배열의 중간값을 변수에 지정해줍니다.

#5 중간값이 target과 같다면 중간값을 반환합니다.

#6 중간값이 target보다 크다면, target은 nums 배열에서 [0, ... , mid] 사이에 있는 것이므로, last_idx 값을 mid-1로 업데이트 합니다.

#7 중간값이 target보다 작으면, target은 nums 배열에서 [mid, ... , last_idx] 사이에 있는 것이므로, start_idx 값을 mid+1로 업데이트 합니다.

#8 while문의 조건이 거짓이 될 때까지 위의 과정을 반복하여 값을 반환합니다.

def answer(nums, target):
	#1
    start_idx = 0
    last_idx = len(nums) - 1
	
    #2
    result = -1
	
    #3
    while start_idx <= last_idx:
        #4
        mid = (start_idx + last_idx) // 2
		
        #5 // #8
        if nums[mid] == target:
            result = mid
            return result
		
        #6
        elif nums[mid] > target:
            last_idx = mid - 1
		
        #7
        else:
            start_idx = mid + 1

    return result
profile
누구나 이해할 수 있도록

0개의 댓글