[Algorithm] 이진 탐색(Binary Search)

얼마전 신입을 채용하는 회사에 서류 전형에 합격해 오늘 코딩테스트를 봤는데 결과가 매우 처참하다..

총 4문제 중 마지막 문제는 앞에 3문제를 푸느라 손도대지 못했고 나머지 3문제도 제대로 풀었다고 할 수 없는 수준이였다.

시험이 끝나고 비슷한 문제가 있는지 검색을 해보는데 특정 알고리즘을 이용해야 풀 수 있는 문제라는것을 알게 되었다. 평소 단순 구현 문제만 풀었던게 발목을 잡았던것이였다. 그래서 이제라도 알고리즘을 공부해야 겠다는 생각을 하게 되어 알고리즘에 대한 포스팅을 시작하려고 한다.

오늘은 이진 탐색에 대해 알아보고 이진 탐색 관련 문제를 LeetCode를 통해 3문제 풀어봤다.

LeetCode문제 선별은 개발바닥 2사로 카톡방에 허재님이 공유해주신 LeetCode 스터디 플랜을 활용하였습니다.

이진 탐색

이진탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

예를 들어 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]처럼 10개의 숫자가 정렬 되어 있는 리스트가 있고 7이라는 숫자를 찾는다고 가정하자.

여기서 숫자 8을 찾는 방법으로는 1부터 차례대로 검색하는 방법도 있겠지만 이진탐색 알고리즘을 이용해보자.

우선 1 ~ 10의 중앙값인 5를 선택한다. 그리고 이 중앙값 5와 찾으려는 값 7을 비교한다. 찾으려는값이 중앙값 보다 크니 1 부터 5사이의 숫자는 더이상 검색할 필요가 없어진다. 그러면 다시 6 ~ 10의 중앙값인 8을 선택한다. 그리고 또 다시 중앙값 8과 찾으려는 값 7을 비교해본다. 이번엔 찾으려는 값이 더 작으니 8부터 10사이의 숫자는 검색할 필요가 없어진다. 그럼 남은 숫자는 6과 7인데 마지막으로 비교해서 찾으려는 숫자 7을 찾을 수 있다.

만약 1부터 하나씩 비교해서 7을 찾으려면 총 7번을 비교하는 비용이 발생했겠지만 이진탐색을 사용하니 3번만에 찾으려는 수를 찾을 수 있었다. 시간 복잡도 개념에서도 for문을 이용해 한번씩 찾는 방법은 O(N)이지만 이진탐색 알고리즘의 시간복잡도는 O(logN)이다.

그림을 통한 예시