[algo] 이진탐색이란?

letsbebrave·2022년 4월 7일

알고리즘 이진탐색 코딩테스트

algorithm

목록 보기

2/16

이진탐색

정렬되어 있는 배열에서 데이터를 찾으려고 시도할 때, 탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법

이분탐색(이진탐색/binary search)의 기본조건은
원소가 오름차순이나 내림차순으로 정렬된 배열에서 사용 가능하다는 것!

핵심은 target은 그대로이고, start와 end가 계속 움직이면서 mid 인덱스의 값과 target이 같아질 때까지 이동한다는 것!

이진탐색의 시간복잡도 및 빅오 표기

O(logN)

N개의 크기 배열을 이진 탐색하면 N, N/2, N/4, N/8, … , 1 으로 실행됨. 여기서 실행된 탐색의 횟수가 시간 복잡도가 될 것이고 그 값을 K라고 한다면

1에 2를 K번 곱하면? N이 된다.
2^K = N
K = log2N

즉, 이진 탐색의 시간 복잡도는 O(logN) 이 된다.

구현 위한 준비

target : 찾고자 하는 값
data : 오름차순(내림차순)으로 정렬된 list
start : data 의 처음 값 인덱스 (but 인덱스가 아니고 그냥 값일 수도 있음!)
end : data 의 마지막 값 인덱스
mid : start, end 의 중간 인덱스

구현 개요

자료의 중간 값이 (mid) 찾고자 하는 값인지 검사
아니라면 대소관계를 비교하여 start, end 값 이동
동일 연산 반복 (재귀로 구현 가능)

if data[mid] == target:
  	return mid # 함수를 끝내버린다 // 타겟이 있으면 인덱스 리턴
elif data[mid] < target: # 타겟보다 data[mid]가 작으면 data[mid]가 더 커져야 하는 것이므로 start = mid + 1
  	start = mid + 1
else: # 타겟보다 data[mid]가 크면 data[mid]가 더 작아져야 하는 것이므로 end = mid - 1
 	 end = mid -1

코드로 표현

data 중에서 target을 검색하여 맞으면 index 값을 return
없으면 None을 리턴

1. while start <= end:

# 바이너리 서치
# data 중에서 target 을 검색하여 index 값을 return 한다.
# 없으면 None을 return한다.

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다 // 타겟이 있으면 인덱스 리턴
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None # 타겟이 없으면 while문을 빠져 나오므로 None을 리턴

# 테스트용 코드
if __name__ == "__main__":
  li = [i**2 for i in range(11)]
  target = 9
  idx = binary_search(target, li)

  if idx:
      print(li[idx])
  else:
      print("찾으시는 타겟 {}가 없습니다".format(target))

2. 재귀적 구현

# data는 오름차순으로 정렬된 리스트
def binary_search_recursion(target, start, end, data):
    if start > end:  # 타겟이 없으면 None을 리턴 (재귀 종료 조건)
        return None 

    mid = (start + end) // 2

    if data[mid] == target:
        return mid # 타겟이 있으면 인덱스 리턴
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, end, data) # 함수 내에서 start, end 조정해준 다음 해당 값을 똑같이 호출해줌

# 테스트용 코드
if __name__ == '__main__':
    li = [i*3 for i in range(11)]
    target = 6
    idx = binary_search_recursion(target, 0, 10, li)

    print(li)
    print(idx)

구현 연습

# while문으로 이진탐색 구현
def bsearch(target, data):
    # data 중에서 target을 찾는 것
    data.sort()
    start = 0
    end = len(data)-1
    # mid = (start + end) // 2 (X)
    
    while start <= end:
        mid = (start + end) // 2  
        # mid는 if문 대소비교로 바뀌는 start, end의 값에 따라 계속 갱신되어야 하므로
        # while문 안에 있어야 함
        if data[mid] == target:
            return mid
        elif data[mid] > target:
            end = mid - 1
        elif data[mid] < target:
            start = mid + 1
    
    return None # target이 없으면 whlie문 빠져 나오므로 None을 리턴

target = 0
data = [1,2,3]
# 재귀로 이진탐색 구현
# 힌트 : 재귀함수의 매개변수에는 start, end, target, data가 들어간다
def bsearch2(start, end, target, data):
    if start > end: # 재귀 종료 조건
        return None
    
    mid = (start + end) // 2
    
    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    elif data[mid] < target:
        start = mid + 1
    
    return bsearch2(start, end, target, data) # 리턴을 안 해주면 마지막에 값을 가져올 수가 없음
 
data.sort()   
bsearch2(0, len(data)-1, target, data)

이진탐색 문제 풀이 시 기준 잡기

보통 문제에서 ~의 최대 길이, 두 합이 0에 가장 가까운 것, 달성할 수 있는 최대 팀 목표 를 찾으라고 제시가 된다.

이진탐색 문제는 무엇을 기준으로 잡느냐가 가장 중요하다고 볼 수 있는데, 이때 기준으로 잡게 되는 것은
문제에서 구하라는 것을 기준으로 삼으면 된다.

왜냐하면 구하고자 하는 것을 기준으로 잡아야 그것에 수렴하는 최대값 or 최소값 or 특정값에 대해 수렴하는 값을 구할 수 있기 때문이다.

정리하면, 구하라는 것을 기준으로 잡고 그것을 start, end로 나타내기 위해 머리를 굴려보면 된다.
그리고 target에 가까워질 수 있도록 또 코드를 짜주면 된다.

ex.
1. 기준을 문제에서 잡으라는 것을 가지고 짠다.
2. start, end 값을 기준을 가지고 어떻게 해줘야 할지 생각한다.
3. mid 값과 target을 어떻게 비교하고 또 수정해줘야 할지 생각한다.
4. 충족되는 조건에 answer 변수를 달고 계속 갱신시켜준다.