[알고리즘] 이진 탐색 Binary search

1. 이진 탐색이란

정렬된 데이터로부터 효과적으로 타겟을 찾을 수 있는 알고리즘입니다. 
탐색할 자료를 둘로 나누어 찾는 데이터가 있는지 없는지 확인하기 때문에, 데이터가 정렬되어 있을 때 순차 탐색 sequential search보다 훨씬 빠르게 찾을 수 있습니다. 특정 범위 내에서 숫자를 추측하는 guessing game등을 할 때 필승할 수 있는 방법입니다. 
이진 탐색은 분할 정복 알고리즘의 일종이기도 합니다. 1부터 71까지 랜덤하게 존재하는 숫자 배열로부터 7을 찾는 제일 효율적인 방법으로 시각화하면 아래 그림과 같습니다. 

출처: t.ly/xJrM

분할 정복 알고리즘 divide and conquer이란, 문제를 하나 또는 둘 이상으로 나누어 문제를 해결하는 알고리즘입니다. 나눠진 문제가 충분히 작은 상태에서 해결이 가능하면 해결하고 아니라면 다시 나누어 다시 해결합니다. 주로 구현 시 재귀 용법을 사용합니다. 

시간복잡도: $ O(logn) $

1-1. 순차 탐색이란

데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법입니다. 순차 탐색은 최악의 경우 리스트 길이가 n일 때 n번 탐색해야하므로 $O(n)$의 시간복잡도를 가집니다. 

2. 알고리즘 구현 및 문제풀이

on Github 

(22.09.07 20:22 추가) 1920번 문제는 강의에서 들은 대로 문제를 풀었음에도 시간초과의 늪으로부터 빠져나올 수 없었는데, 이유를 스터디원들과 함께 찾았습니다. 재귀함수로 새로운 num_list를 넣어줄 때 slicing을 하면 $ O(b-a) $ 의 시간복잡도를 가진다고 합니다. 탐색을 위한 숫자들이 많으면 많을수록 시간에 불리한 것입니다.  따라서 start point&end point를 잡아서 재귀함수에 리스트 내의 탐색을 위한 시작점과 끝점을 새로 지정해 주는게 시간을 줄이는 데 유리할 것입니다. 

10816문제는 아직 풀이중이지만 아무튼 올려봅니다..😎