이진 탐색 알고리즘이란
절반씩 중앙값을 비교하여 원했던 값을 찾는 알고리즘이다.
2를 찾고 싶다면
1 2 3 4 5 6 7 8 9
F C L
C를 L로 바꾸고 (F+L) / 2를 하여 새로운 중앙 값을 구한다.
1 2 3 4 5
F C L
이후 해당 과정을 반복하여
남은 값이 하나가 될때까지 반복하는 것이다. 마지막으로 남은 값 하나일때 이 값이 2인지 아닌지 판단한다.
2
FCL
즉 최악의 경우는 K(한개가 남기전까지 연산한 횟수)+1(마지막으로 남은 값이 원하는 값인지 확인하기위한 연산)이 되는 것이다.
따라서 생각 해보면 위의 과정들은
배열 n개가 있을때
일때까지가 최악인 것을 알 수 있다.(K는 연산 횟수이다.)
즉
는
이고
해당 수를 k(연산횟수)로 잘 보기위해 로그로 변환한다면
하지만 n이 1조개일때 1억개 + 1의 1은 아무의미가 없기때문에 시간 복잡도에서는 생략한다.
마찬가지로 1조개 +1000개일때도 1000은 너무나 미미한 숫자이기 때문에 생략이다.
즉 우리에게 중요한건 n(배열)이 어떻게 되어있는지가 중요하지 일반 상수는 전혀 의미가 없다.
해당 그래프와 같이 이동하는 것을 볼 수 있다.
즉 X(배열크기)가 커지면 커질 수록 원하는 값을 찾기 위한 연산은 얼마 차이 안난다는 거다.
1조개나 10조개나 원하는 값을 찾는데 1000번이나 1004번이나 별 차이 안난다는거다.
즉 이진 탐색알고리즘은 탐색하는 범위가 커지면 커질수록 일정한 속도를 내기때문에 범위가 큰 값일 수록 사용하기 좋은 것 같다.
