이분탐색

이분탐색

 

N 개의 수가 크기 순서대로 배열되어 있을 때, 특정한 수 K가 몇 번째 위치에 있는지 빠르게 찾는 방법

 

 

• 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

 

한 번에 배열이  절반씩 줄어들기 때문에, 시간 복잡도는 O(log2 N)이다.(밑 2)

N이 100만일 때, log2 N은 약 20이므로 20개 정도의 수만 보면 충분하다