이진검색, 선형검색 알고리즘(Binary Search,Linear Search)

알고리즘 = 어떠한 작업을 수행하기 위해 우리가 따라야 하는 절차와 스텝( 예 : 레시피)

 

알고리즘에도 시간복잡도가 존재

 

적은 스텝과 빠른 스피드인 알고리즘이 훌륭한 알고리즘.

 

 

다른 알고리즘 패밀리로는 Sorting(정렬 알고리즘) 도 있음.

 

ex ) A - Z / 작은수 - 큰수

 

선형검색 알고리즘이란?

 

어찌보면 가장 검색을 하기위한 자연스러운 방법

만약 7을 찾는다고 가정해보자.

 

33,2,20,1,7! 찾았다!

처음부터 끝까지. 순서대로. 차근차근

이러한 선형검색은 최악의 경우 찾는 값이 배열 맨 마지막에 있거나

없을경우 일텐데, 배열이 커지면 커질수록 선형검색을 하는 시간 또한 길어지게 될 것이다.

(하나하나 까본다.) 

 

이를 Linear Time Complexity (선형 시간복잡도) 라고 한다.

 

인풋이 많으면 많을수록

작업 시간도 선형적으로 증가한다는 소리이다.

 

이거보다 발전한 방식이 있는데 바로

 

이진검색 알고리즘(Binary Search)이다.

 

이진검색 알고리즘을 모든 배열에 쓸수 없다. 

 

그럼 어떤 배열에 사용이 가능한가?

 

바로

 

정렬된 배열에만 사용이 가능하다.

어떤 알고리즘은 특정 자료구조에서만 사용이 가능한데 이 이진검색 알고리즘이 대표적이다.

 

선형검색은 어느 배열구조에서 사용가능하지만, 이진검색은 정렬된 배열에서만 사용이 가능하다.

 

그렇다면 SortedArray란 무엇일까? 바로

정렬된 배열 SortedArray

예를들면 1에서 10까지 정렬된경우이다.

그러나 이렇게 정렬된 배열에 아이템을 추가하는 것은

정렬이 안된 경우보다 시간이 더 걸리게된다.

그러나  정렬된 배열에서 검색을 하는 것은 정말 빠르다.

 

정렬이 안된경우보다 말이다.

 

정렬이 안된배열에 값을 추가할 경우

 

공간이 있기만 하면

이렇게 값을 추가하면 그만이지만

 

정렬된 배열에서 아이템을 추가하는 것은

 

만약 2.5.7.10이라는 배열이 있는데 8이라는 아이템을 추가하고 싶다면

 

해당 배열에서 일단 8보다 큰 아이템을 찾아야 한다.

찾은 후 8을 해당 아이템 왼쪽에 추가해야한다.

이 작업을 위해 인덱스 0부터 시작해서 작업을 시작하고

해당 숫자가 추가하고 싶은 숫자보다

큰지 작은지를 각각 비교해야한다.

 

이를 위해서는

 

인덱스 0은 2 -> 통과

인덱스 1은 5 -> 통과

인덱스 2는 7 -> 통과

인덱스 3은 10 -> 찾음!

 

라는 작업의 반복이 필요하다.

10은 8보다 크므로 8을 추가하하고싶은 포지션의

오른쪽에 아이템들을 움직여야 8이라는 아이템을 비로소 집어넣을수 있게 되는것이다

 

 

보다시피 정렬된 배열에 아이템을 추가하는 것이 시간이 더 걸린다.

아이템을 하나하나 비교후 포지션을 찾고나면 아이템 오른쪽에 있는 모든것을 밀어야함

 

하지만 이렇게 시간을 더 투자하면

배열에 추가하고 정렬하는것에 시간을 투자하면 검색을 하는 순간에 보람을 느끼게 될것이다.ㅋㅋ\

 

정렬된 배열에 이진 검색을 해보자.

이진은 말그대로 0 1 을 의미하진 않고 하나를 두개로 쪼개는 의미에서의 이진이다.

 

찾고싶은 값은 9라고 가정을 하면 

 

선형 검색과 달리 이진 검색에서는

인덱스 0부터 시작하지 않는다.

정열의 중간에서 시작하는데 정 가운데 있는 숫자가 큰지, 작은지를 보고

목표보다 크다면 왼쪽으로 가고

목표보다 작다면 아이템의 오른쪽으로 간다.

 

1에서 10까지 정렬된 상황에서 중간은 5이다.

5 < 9니 아이템의 오른쪽으로 이동한다. 

6 7 8 9 10

의 중간인 8로 이동한다.

8 < 9이므로 다시 오른쪽으로 이동한다.

 

3번째 스텝에서 바로 찾게되었다. 9를

딱 3번만에 찾을 수 있다.

 

선형검색이면 9번을 시도했을텐데 말이다.

 

아이템을 늘려 20개로 가정해보자

 

.

 찾는값은 13이라고 가정하고

 

중간점은 10이다.

 

10 < 13이니 왼쪽의 아이템들은 싸그리 무시된다.

자 그럼 11~20중

중앙은 15이다.

15 > 13이니

아이템 왼쪽으로 가게된다.

이때 3번째 스텝에서는

12 < 13이니

아이템 오른쪽으로 가게된다.

4번쩨 스텝에서 13을 찾음. 끝.

 

인풋은 2배가 되었지만 필요한 스텝은 1스텝밖에 증가하질 않았다.

 

이진 검색은 매 스텝마다 절반의 아이템을 날려버리기 때문이다.

이는 엄청 효율적이다. 큰사이즈의 데이터를 처리할때 특히.

1만개의 아이템이 있는 선형검색은

최악의 경우 1만개의 스텝이 필요하다. (다 까봐야하기 때문, 없을수도 있고)

반면 1만개의 아이템을 지닌 이진검색은

최악의 경우에도 14스텝만 필요하다.

매 스텝 반씩 없애버리고 왼쪽으로 갈지 오른쪽으로 갈지 찾기 때문이다.

이진검색은 거대한 배열을 다룰때 효율적이지만

 

배열을 정렬할 필요가 있고

 

이는 시간이 소요되는 일이다.

바로 여기서 트레이드 오프(등가교환쯤.. 되는듯)

검색을 많이 해야하는 상황이라면 일단 정렬을 해야하고

 

하지만 배열 정렬을 하려면

 

아이템도 추가하는 등.. 시간이 소요되기 마련이다.

이러한 상충관계를 명확히 인지하기 위해 알고리즘, 데이터 구조를 알아야한다.