검색(Search) 알고리즘 이란?

검색(Search)이란?

• 검색 알고리즘 이란?
  정의 : 데이터 집합에서 특정한 데이터를 찾는 문제를 해결하는 알고리즘이다.
  

• 검색 알고리즘 종류
  - 선형 탐색
  - 이진 탐색
  - 해시
  
  

---

선형 탐색(Linear Search) 알고리즘

• 정의 : 배열 전체를 하나씩 확인해 가며 탐색하는 알고리즘
  
  
• 시간 복잡도 : O(n)
• 특징
  • 모든 데이터 타입에 사용 가능 (문자열, 숫자,…etc)
  • 데이터의 양 n만큼의 저장 공간이 필요
  • 찾으려는 데이터가 마지막에 있을경우 n의 시간 복잡도를 갖는다.

---

이진 탐색(Binary Search) 알고리즘

• 정의 : 전체 배열의 중앙을 비교하여 찾으려 하는 값이 작으면 왼쪽 크면 오른쪽 에서 부터 다시 탐색하는 방법으로 , 탐색양을 절반씩 줄여가며 찾는 탐색 알고리즘 이다.
  
  
• 시간 복잡도 : O(log n)
• 특징
  • 전제 조건
    • 미리 정렬이 되어 있어야 한다
    • 입력시마다 재정렬을 필요로 한다
    • 데이터의 비교가 가능해야 한다.(ex 숫자..etc)
  • [ 출력 < 입력 ]의 상황시 입력시 마다 재정렬을 해야하기 때문에 느려질 수 있다.

• BinarySearch Algorithm

  class BinarySearch {
      public static int binarySearch(int target, int arr[]) {
          int mid;
          int left = 0;
          int right = arr.length - 1;
  
          while (right >= left) {
              mid = (right + left) / 2;
  
              if (target == arr[mid]) {
                  return mid;
              }
  
              if (target < arr[mid]) {
                  right = mid - 1;
              } else {
                  left = mid + 1;
              }
          }
          return -1;
      }

  
  

---

해시 탐색(Hash Search) 알고리즘

• 정의 : 해싱함수를 통해 얻은 해시값을 저장 위치로 삼아 데이터를 탐색하는 방법

• 시간 복잡도 : O(1)

• 특징

  • HashMap or HashTable 사용
  • 모든 데이터에 사용이 가능하다
  • 해시 충돌의 수를 줄이기 위하여 데이터 n 이상의 저장 공간이 필요하다
  • 해시 충돌이 일어날 경우
    • 해시충돌을 어떻게 예방 하느냐에 따라 시간복잡도가 변경될 수 있다
      • chaining 기법
      • open addressing 기법
        Hash관련 velog 정리
  
  

---

탐색 알고리즘 필요 상황

• [ 데이터 삽입 < 데이터 탐색 ] → 이진 탐색이 유리
• [ 데이터 삽입 > 데이터 탐색 ] → 선형 탐색이 유리
• 데이터를 저장할 메모리 공간을 많이 사용 가능하다. → 해시