코딩 연습

주어진 배열에서 특정한 요소 target 을 찾아내는 상황을 가정해 봅시다. 가장 쉽게 떠 올릴 수 있는 방법은 배열의 요소 하나하나와 target 값이 같은지를 순차적으로 모두 비교하는 것입니다. 만약 배열의 크기가 $n$ 이라고 한다면 이 알고리즘의 시간복잡도를 Big-Oh notation을 이용하요 나타낸다면 $O(n)$ 이 되겠죠. 그렇지만 이것보다 훨씬 빠르게 target 을 찾아내는 방법도 있습니다. 우리가 살펴봐야 할 요소들의 개수를 절반으로 줄여가면서 탐색을 하는 것이죠. 이런식으로 탐색하는 방법이 바로 이진 탐색 알고리즘입니다. 다만 이진 탐색(binary search)은 오름 차순으로 정렬된 배열에만 적용할 수 있다는 단점이 있습니다. (앞으로 내용을 보시면 아시겠지만 오름차순으로 정렬..