이분 탐색(Binary search) 개념

알고리즘 공부할 때, 빈번하게 나오는 유형이 아니다보니 매번 공부를 미뤘다.

이젠, 시간에 쫓기지 않아도 되니 조금씩 다뤄볼 예정이다 !

 

이분탐색

이분 탐색이란 말그대로 정렬된 리스트에서 검색 범위를 줄여나가며 특정 값을 찾는 알고리즘이다.

 

왜 사용 ?

검색이 반복될 때마다, 범위를 절반씩 줄여나갈 수 있기 때문에 시간복잡도 O(logN)이다. 범위 절반씩 줄기 때문에, 당연하다.

 

투 포인터(Two Pointer)와 무슨 차이 ?

조금 깊게 생각해보면 차이를 확연히 느낄 수 있다.

	이분 탐색	투 포인터
시간복잡도	O(logN)	O(N)
조건	정렬된 리스트	상관없음
방식	mid를 활용해서 범위를 절반씩 줄여나감	start, end 사용해서 한 칸씩 이동

정렬되지 않은 리스트에서 특정한 값을 찾아야한다면, 투 포인터가 유리할수도 있기 때문에, 알맞은 상황에 쓰면 된다.

 

이분탐색 코드 구현

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

다음과 같은 로직으로 짜진다.

start와 end를 통해 mid를 구한 후, 

우리가 찾고자 하는 값(tar)이 위치(중앙)의 값과 같으면, mid를 반환하고

그렇지 않다면, 투 포인터처럼 start와 end를 움직여준다 !

 

 

예제 풀어보기 

 

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

# 이분탐색 x => 시간초과 코드
n = int(input())
lst = list(map(int,input().split()))
m = int(input())
tar = list(map(int,input().split()))

ans = []
for i in tar:
  if i in lst:
    ans.append(lst.count(i))
  else :
    ans.append(0)
print(ans)

당연한 결과지만, O(N^2)이므로 시간초과가 났다. (반복문에서 n, count에서 n)

딕셔너리를 이용하면 해결된다..! but 나의 목적은 그게 아니기 때문에,,^^

이분탐색을 적용하려고 했으나, 어떻게 tar의 개수를 O(NlogN)으로 세는지 감이 잡히지 않았다.

이분탐색을 적용했으나, O(N^2)로 코드가 짜졌다 ㅋㅋㅋ ㅠㅠ

 

그래서 그냥 다른 분들의 코드를 보면서 익히려고 한다. 

 

## 다른 분 풀이 참고
def binary(n, N, start, end):
    if start > end:
        return 0
    m = (start+end)//2
    if n == N[m]:
        return N[start:end+1].count(n)
    elif n < N[m]:
        return binary(n, N, start, m-1)
    else:
        return binary(n, N, m+1, end)

target을 찾으면 start부터 end까지에서 count를 적용해준다..

나는 바보같이 이분 탐색을 적용하고 쓰질 못했다 

 

로직을 파악하고, 코드를 다시 짜봤다

"""
실버 4 :
첫 시도 : 시간 초과 (이분 탐색을 적절히 사용 x)

결국, 다른 사람의 풀이를 참고하였음
"""

## 정답 전체 코드
import sys
input = sys.stdin.readline

def bs(lst, tar, start, end):
  #start, end가 들어오면, lst에서 tar를 찾자
  mid = (start+end)//2
  if start > end: # 다 돌았는데, tar이 없는 것
    return 0 
  if tar == lst[mid] : #찾으면
    return lst[start:end+1].count(tar)
  elif tar > lst[mid]:
    return bs(lst, tar, mid+1, end)
  else :  
    return bs(lst, tar, start, mid-1)  
    
n = int(input())
lst = list(map(int, input().split()))
lst.sort()
m = int(input())
target = list(map(int, input().split()))

dic = {}
start,end = [0, len(lst)-1]
for i in lst:
  if i not in dic:
    dic[i] = bs(lst, i, start, end)

print(dic)
print(' '.join(str(dic[x]) if x in dic else '0' for x in target ))

내가 틀렸던 이유는 아래와 같다.

1. count를 모든 범위에 사용하여 O(N)만큼 소요

2. 딕셔너리를 사용하지 않음

## 시간 초과
for i in target:
  if i not in lst: ## 이것도 사실 IN 보단, bs에 넣는게 시간은 더 효율적일듯
    ans.append(0)
  else:
    ans.append(bs(lst, i, start, end))

처음엔 ans 스택을 만들어주고, tar 리스트를 반복문을 돌려 하나의 값씩 추가해주었다. 이분 탐색을 이용했음에도 불구하고 이것 또한 시간 초과가 일어났다. 

그 이유는 많은 양의 값들을 리스트에 append하기 때문에 시간초과가 난 것 같다.

(솔직히 이해 안 됨. 스택에 append도 O(1)이고, 딕셔너리에 값을 넣는 것도 O(1) 아님??

어짜피 target 리스트를 반복 돌려서 스택에 추가하면 , 중복된 값도 없고

lst에서 딕셔너리에 있는지 확인 후 추가하면, 마찬가지로 중복된 값 없음

그럼 비슷해야하는거 아닌가..

)

 

==> 해결했다 !!!!!!!

정말 간단한 문제였다.

리스트의 in은 O(N)이고, 딕셔너리의 in은 해쉬를 사용하기 때문에, O(1)이었음

 

딕셔너리를 이용해 append하지 말고, 넣어주자 !