이분 검색(Binary Search) 삽입시 개선점

이분 검색의 삽입방식은 맨 끝에 요소를 놓고 노말하게 삽입정렬을 하는 방식이다.

이 부분을 조금 더 빨리 개선할 수 있는 점이 보인다.
이미 정렬된 상태이므로 find와 유사한 함수를 만들어 들어갈 자리를 쉽게 찾을 수 있으리라 본다.

가령 1,3,5,9,11 등에서 7을 집어 넣는다 할 때
우선 7을 찾아보면
인덱스 2 중간값 5보다 큰 수이므로 오른쪽으로 가고
인덱스 3 중간값 9보다는 작으므로 다시 찾는 루틴을 시도하지만 조건 불만족으로 탈출할 것이다.
탈출시 조사한 곳의 mid값을 가지고 위치판단이 가능할 것이다.

위와 같은 식으로 자리를 찾는 수고를 덜 수 있으리라 본다. 찾을 때 O(N)을 O(lon(2)N) 수준으로 줄인다.
그 뒷자리 메모리를 일괄적으로 한칸씩 미는 수고는 어쩔 수 없지만,,,,,