고정된 데이터들의 탐색 vs 회전하는 데이터들의 탐색

고정된 데이터들의 탐색

[1,2,3,4,5]의 배열이 있다. 

전제

1. 데이터들이 오름차순으로 정렬이 되어 있다.

2. 데이터들의 위치가 바뀌지 않고, 고정이 되어있다.

-> 걍 이진 탐색(Binary Search)를 사용하면,O(logn)의 time complexity로 탐색하면 된다.

 

회전하는 데이터들의 탐색

[1,2,3,4,5] --->  [4,5,1,2,3] 

전제

1. 초기에는 오름차순으로 이미 정렬이 돼 있는 상태이다.

2. 오른쪽으로 2칸 회전됨.( deque로 회전을 구현 가능)

이떄, 배열은 2가지 종류의 정렬된 배열로 분할 가능 : [4,5] , [1,2,3]

 

회전하는 데이터들의 탐색 알고리즘

step 1. start end를 이용하여 mid값을 구한다.

step 2. (mid값 >= start)

if ( start <= 찾는 데이터 <= mid값) ==> start와 mid 사이의 데이터들([4,5])에 대해 이진 탐색

else if( mid값 < 찾는 데이터 ) ==> mid의 오른쪽 부분[(1,2,3])에 대해 이진 탐색

step3 (mid값 < start)

if( 찾는 데이터 >= start ) ==> mid의 왼쪽 영역([4,5])에 대해 이진 탐색

else if( 찾는 데이터 < start ) ==>  mid의 오른쪽 영역( [ 1,2,3])에 대해 이진 탐색

step 4

if( start > end) ==> 찾는 데이터가 배열에 존재하지 않음!!

 

 결론 : 회전하는 데이터에도 이분 탐색을 적용할 수가 있다.