슈퍼개발자, 춤추는망고입니다.

( 춤 안춥니다. )

앞으로 이 시리즈는 짤막하지만 실용적인 내용들을 담을겁니다!

더 효율적인 탐색!

??? : 난 둘다 괜찮은데?

선형탐색과 이진탐색 !

갑자기 왠 탐색 ?

선형탐색, 이진탐색

개발 쪽으로 공부를 시작한 뒤, 어디선가 들어본 적이 있었는데요...
공부해야지...공부해야지... 마음만 먹고 있었어요... ㅜㅠ

그런데 마침, 알고리즘 공부를 하다가 이 개념이 뙇!

( 선형탐색과 이진탐색이라는 개념은, 오름/내림 순서대로 정렬된 요소에만 적용 가능해요! )

먼저, 선형탐색부터 알아보죠 !

선형탐색이란 ?

Linear Search

선의 형태 ( linear ) 로 진행되는 탐색이에요 !

첫 index 부터 하나하나 찾아나가는 방법이죠 !

( for 문으로 사용할 수 있는 간단하고, 자주쓰이는 방법이죠 ! )

선형탐색으로도 충분하지 않아?

음... 만악에 말이죠?

[1,2,3,4,5,6,7,...,100000]

이렇게 긴 배열에서
1 을 찾을때는 모르겠지만,
9000 을 찾아야한다면...

반복문의 명령이 9000번 반복되요 .

( for 문이 9000번? )

이때,

이진탐색법이 있다면 ?!

이렇게 !

처음부터 하나씩 찾는거보다 훨씬 효율적이죠 !

( 느낌이 오시나요 ? )

이진탐색법이란 !

선형탐색법이 처음부터 순서대로 찾는 방법이라면,
이진탐색법은 탐색범위를 반으로 나눠서 찾는 방법이에요 !

1. 찾아야할 내용 ( t ) 을 중간지점의 값 ( m ) 과 비교 !
2. t 가 m 보다 작으면, 시작 - 중간 지점을,
   t 가 m 보다 크면, 중간 - 마지막 지점을 기준으로 다시 탐색 !
3. 이 과정을 반복 !

( 위에 있던 그림처럼 진행되요 ! )

검색범위를 줄여나가며 찾는 방법이죠 !

그래서 장점은 ?

넓은 범위에서 정보를 찾을 때,
선형탐색보다 훨씬 더 적은 연산으로 원하는 결과를 얻을 수 있어요 !

더 복잡한 알고리즘을 위해 배워두면 좋겠죠 ?