Chapter 7. 이진탐색

1. 순차탐색:

 

리스트 안에 있는 특정한 데이터를 찾기 위해서 앞에서 부터 데이터를 하나씩 차례대로 확인하는 방법

count()메서드 또한 순차탐색이 이용된다.

 

 

2. 이진탐색:

 

이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용 할 수 있는 알고리즘이다.

변수 3개를 사용하는데 시작점, 끝점 그리고 중간 점을 이용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진탐색 과정이다.

 

시간 복잡도는 O(nlogn)이다. (한번 확인할때 마다 확인하는 원소의 개수가 절반씩 줄어들기 때문)

 

이진탐색 쉽게 보지 말자!!!

 

'존 벤틀리'(생각하는 프로그래밍의 필자) 의 말에 따르면 제대로 이진 탐색 코드를 작성한 프로그래머는 10% 내외라 할 정도로 실제 구현은 까다롭다.

 

 

-bisect-이진 탐색을 제대로 짜는 것 또한 중요하지만 파이썬으로 알고리즘을 준비하는 사람이라면 매우 유용하게 쓰일 것 같다.bisect 라이브러리는 이진 탐색을 쉽게 구현 할 수 있도록 제공된다.

 

array 가 정렬되어 있을때from bisect import bisect_left, bisect_right 를 임포트 하고bisect_left(array,x) 라고하면 x 가 삽입될 수 있는 인덱스의 위치 중에서 가장 왼쪽 인덱스를 반환한다.bisect_right(array,x) 라고 하면 x 가 삽일될 수 있는 인덱스의 위치 중에서 가장 오른쪽 인덱스를 반환한다.

 

이때 삽입될 index를 알았으니 삽입하거나 그다음 작업을 하면 될 것이다. (list에서 원소를 삽입하는 insert()메서드를 기억하자)