이진 탐색은 배열 속에 내가 원하는 자료가 있는지 찾는 방법이다. 탐색 구간을 둘로 나누어 실행하며 이를 반복해나가기 때문에 이진 탐색이라고 부른다. 책을 펼쳐서 내가 원하는 페이지를 찾는 과정과 아주 비슷하다. 우선 길이가 10인 arr이라는 배열이 아래와 같이 있다고 해보자. 배열이 정렬되어있지 않기 때문에 내가 원하는 값이 어디에 어떤 규칙으로 있는지 알 수 없다. 이 배열에서 자료를 찾으려면 앞에서부터 순차적으로 찾아야 한다. 이걸 선형 탐색(Linear Search)라고 한다. 8을 찾는다면 적당히 5번의 비교로 끝나겠지만 5를 찾는 경우 최악의 상황으로 배열 내 모든 데이터를 확인해야 한다. 따라서 이 방법은 시간 복잡도가 O(n)이다. 사실 이 정도의 시간복잡도가 그리 나쁘지는 않지만 배열의..