이분 검색이란?(What is binary search?) 이전 포스팅에서 작성한 순차 검색은 최대 n이라는 시간이 걸리는 검색 방법이다. 그렇기에 n이 100만, 1000만이 되면 검색하는데 상당히 많은 시간이 소요된다. 이를 해결하기 위한 알고리즘이 바로 이분 검색이다. 이분 검색은 대표적인 분할 정복 알고리즘이다. 이러한 분할 정복 알고리즘은 반복문으로 고쳐주면 더 빠른 성능을 낼 수 있다. 이분 검색의 작동 방식은 다음과 같다. 배열의 중간 요소와 찾고자하는 값을 비교한다. 이때 찾고자하는 값이 배열의 중간 요소이면 값을 리턴하고 종료한다. 배열을 반으로 나눈다. 중간 요소를 기준으로 찾는 값이 작으면 왼쪽 배열을, 크면 오른쪽 배열을 탐색한다. 1~3을 반복한다. 이분 검색 알고리즘(Binary..
