[자료구조] 기본 탐색 - 선형탐색, 이진탐색 방법

자료구조 탐색방법

선형탐색 (Linear Search)

• 처음부터 하난하나 비교하여 검색하는 방법
• 장점 : 구현이 쉽고, 정렬이 안되어있어도 된다.
• 단점 : 검색시간이 오래걸려서 느리다
  예시) 배열 = [ 1 ~10] 이 있고 9를 찾는다면 → 1부터 10까지 9가 나올때까지 순서대로 탐색한다.
  

이진탐색 → 이진트리 & 이진탐색트리에 대한 예시와 설명

이진탐색(Binary Serch)

• 분할정복 방법 : 반씩 범위를 나누어 가면서 분할정복하여 필요없는 ****부분은 버리고 찾는 값을 찾아가는 방법
• 장점 : 속도가 빠르다.
• 단점 : 자료구조안의 데이터가 정렬이 되어있어야한다.
  예) 배열 = [ 1 ~10] → 만약 9를 찾는다면?
  → 이제 가운데 값은 6부터 10의 중간인 8이 된다.
  → 가운데 값인 8과 찾는 값 9를 비교하여 8이 작다면? 8까지의 배열요소를 버린다.
  • 짝수개의 요소일때는 보통 중간에서 앞에 값을 중간값이라 한다.
    → 9, 10 중 중간값은 9이고 9와 찾는 값 9가 같다! 찾음

• 만약 10을 찾는 중이여서 갖지 않았다면 9을 버리고 유일한값 10만 남아서 찾게된다.
  

출처
코딩하는 거니 https://www.youtube.com/watch?v=Vfg6-AWGsCw&list=PLLcbGhhl4sQCiZxLuqDDDH6q-rc4wyaKe&index=7
코드스테이츠