파이썬 이진검색

파이썬 코딩테스트 & 기술면접 뽀개기 (4)

이진검색 관련 leet 문제
(박상길님의 ‘파이썬 알고리즘 인터뷰’ 책 참고)

SoniaComp/Algorithm

이진검색

정렬된 배열에서 타겟을 찾는 알고리즘이다.

시간복잡도

O(log n)

주의: 자료형을 초과하지 않는 이진검색 코드

파이썬은 오버플로우가 없지만, 주의해야 한다!

mid = left + (right — left) // 2

index와 이진검색

• index 메소드 사용: 값이 존재하지 않으면 에러가 발생하므로 예외처리를 할 수 있다.
• 앞에서 부터 차례대로 찾는 index()함수는 최악의 경우 O(n)으로, 뒤에 위치한 값잀록 점점 찾는 속도가 느려지며, 이처럼 1000배나 가까이 차이가 나는 경우도 생길 수 있다.
• 반면 이진검색은 항상 일정한 속도를 보인다. O(logn)으로, 아무리 큰 값이라도 속도 차이가 거의 없다. 로그의 효과 떄문이다.