[CS/알고리즘] 이진 탐색 (Binary Search)

📁 이진 탐색 (Binary Search)

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

✔️ 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘

✔️ 찾으려는 데이터와 "중간점" 위치에 있는 데이터를 반복적으로 비교하는 방법

중간점이 실수일 때는 소수점 이하를 버린다.

 

✔️ 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다. 

✔️ 시간 복잡도 : O(logN)

     → 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다.

💡 코딩테스트 
데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자. 

 

📌 python code (while)

📌 python code (recursive)

 

 

 

---

Ref.

- 이것이 취업을 위한 코딩 테스트다 with 파이썬