이진 탐색_ binary search

정렬된 원소 리스트를 받고 리스트에 원하는 원소가 있으면 그 원소의 위치를 반환하고, 아니면 null 값을 반환한다.

동작방법

1~100 사이의 숫자를 맞추세요

단순 탐색은 1,2,3,... 차례로 답을 말하는 거지만 이진 탐색은 1~100사이의 중간인 50 부터 시작하여 50이 작다고 대답하면 51~100사이의 숫자중 중간에 속하는 75로 추측한다. 이런식으로 남아있는 숫자의 중간에 속하는 숫자들로 탐색하여 정답을 추론한다.

단순 탐색이라면 100번만에 정답을 찾을수 있지만 , 이진 탐색은 7번만에 정답을 찾을수 있다.

만약 n개의 원소를 가진 리스트에서 이진 탐색을 사용하면 최대 log₂n번만에 답을 찾을수 있다. 단순 탐색이라면 n번이 필요 할수 있다.

로그

log10 100 

10을 몇번 곱해야 100 이 되는 지 묻는 문제 이다. 10x10 = 100 이므로 정답은 2이다.
즉 로그는 거듭제곱의 반대말 이다.

거듭제곱	로그
10²=100	log10 100 = 2
10³=1000	log10 1000 = 3
2³=8	log₂8=3
2⁴=16	log₂16=4
2⁵=32	log₂32=5

실행시간 runnig time

100개의 원소가 있는 경우 몇번을 탐색해야 하는가?

단순탐색은 숫자를 하나하나 확인하는 것인데 100개라면 100번을 추측해야 한다. 추측해야할 최대 횟수가 리스트의 길이와 같은데 이런것을 선형 시간(liner time)이라고 한다.

이진탐색은 7번만 추측해도되는데 이러한경우는 로그 시간(logarithmic time)으로 실행된다.

이진탐색은 시간 절약을 해준다!

빅오표기법(Big O notation)

알고리즘이 얼마나 빠른지 표시하는 특별한 방법

이진탐색과 단순 탐색의 실행 시간이 같은 비율로 증가 하지 않는다!

원소의 개수가 증가해도 이진탐색에 걸리는 시간은 얼마 늘어나지 않지만 단순탐색의 시간은 엄청나게 증가한다. 그러니까 원소의 개수가 커질수록 이진탐색은 단순 탐색보다 훨씬 빨라지는 것이다.

이진탐색 > 단순탐색 (속도)

동작방법

리스트 크기가 n이 라고 가정할때 , 단순 탐색은 n번을 연산한다. 그래서 빅오 표기법에 따른 실행 시간은 O(n)이다. 빅오 표기법은 속도를 시간 단위로 세지 않는다. 단지 연산 횟수를 비교하기 위한 것이기때문이다.

다른예로는 이진 탐색이 n인 리스트를 확인하기 위해 log n번의 연산이 빌요하다. 빅오표기법으로는 O (log n)이다.

빅오 표기법

O (연산횟수)

많이 사용하는 빅오 실행 시간의 예

O(log n)

• 로그시간
• 이진탐색
  

O(n)

• 선형시간
• 단순탐색

O(n*log n)

• 퀵정렬과 같이 빠른 정렬 알고리즘

O(n²)

• 선택정렬과 같이 느린 정렬 알고리즘

O(n!)

• 정말 느린 알고리즘

요약

• 이진 탐색은 단순 탐색보다 빠르다
• O(log n)은 O(n) 보다 빠르다. 리스트의 원소의 개수가 증가 하면 상대적으로 더 빨라진다.
• 알고리즘의 속도는 시간으로 측정하지 않는다.
• 알고리즘의 시간은 어떻게 증가하는가로 측정한다.
• 알고리즘의 시간은 빅오 표기법으로 나타낸다.

---

참고

'Hello Coding 알고리즘' 책을 공부하여 요약정리한 내용입니다.