본문 바로가기

Binary search

Binary search, 이진 탐색 리스트 A = [ 0, 1, ,2, 3 ] 이 있을 때, 마지막 원소인 '3'을 찾는다고 해보자. Simple search, 단순 탐색의 경우처음부터 순차적으로 원소 값을 확인한다. 마지막에 위치하고 있는 원소인 '3'을 찾기 위해서는 리스트의 길이와 같은 시간이 걸린다. 리스트의 길이와 같은시간을 O(n), linear time 선형시간 이라고 한다. Binary search, 이진 탐색은리스트의 중간에 있는 원소의 크기에 따라 탐색할 구간(range)를 반씩 줄여나가 O(log n), logarithm time 로그 시간이 걸리는 방식이다. 만약 100개의 원소를 가지고 있는 리스트라면 탐색할 구간이 100 에서 50, 25, 13, 7, 4, 2, 1 순으로 줄어든다. 따라서, A의 중간에 위치한 .. 더보기

티스토리툴바