바이너리 서치에 관한 문제입니다.

배열에 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11 이런식으로 오름차순이 되있는 상태에서

바이너리 서치를 할 경우 O(log(n)) 의 시간복잡도가 나오는데요

제가 당황했던 부분은 배열의 한 뭉태기가 잘못 넣어진 경우

예를 들어 위의 배열을 다음과 같이 바꿨을 때

1, 2, 8, 9, 10, 3, 4, 5, 6, 7, 11

이때 배열에서 8 이란 숫자를 찾고 싶을때

순차검색이 시간복잡도가 O(n) 이 나오는데

시간복잡도가 n 보다 작게 나올 수 있는 바이너리 서치 알고리즘이 있을까요?

혹은 다른 알고리즘이 있을까 궁금하네요

제가 면접때 위의 질문을 받았는데 아직까지 궁금합니다.