검색 알고리즘이란?

주어진 데이터 세트에서 원하는 값을 찾는 과정을 정의한 규칙 또는 절차의 집합이다.

• 검색 알고리즘의 핵심은 동등 비교 연산(==)이다.

• 비교 연산을 적게 수행하는 검색 알고리즘이 Best!!이다.

🎯 선형검색

일렬로 나열되어 있는 데이터를 순차적으로 탐색하면서 원하는 값을 찾아내는 알고리즘이다.

• 선형 검색은 구현이 쉽고 리스트의 정렬 여부와 상관없이 동작한다.

• 리스트의 모든 요소를 확인해야 하기 때문에 검색할 리스트의 길이가 길면 비효율적이다.

• 선형 검색의 종료 조건은 검색을 실패할 경우와 검색을 성공할 경우, 두 가지가 있다.
  두 가지 조건 중 하나라도 성립하면 검색을 종료한다.

<구현>

  n = 0
  while True:

      # n이 마지막 인덱스 다음 칸까지 갔으므로
      # 찾는 값이 검색 자료 내에 없다.
      if n == len(datas):
          searchResultIdx = -1
          break 👉 # 검색 종료 조건1. 검색 실패 

      elif datas[n] == searchData:
          searchResultIdx = n
          break 👉 # 검색 종료 조건2. 검색 성공

      n += 1

🎯 보초법

반복의 종료를 알리는 특정한 값인 보초 값을 사용하여 종료 조건중 검색 실패 조건을 제거하는 방법이다.

• 찾는 값을 리스트의 맨 끝 자리에 추가하고 이를 보초 값으로 사용한다.

• 찾으려는 값인 보초 값을 검색하면서 "종료 조건 1(검색 실패)"을 만족하게 된다.

이미지 참고 사이트

<구현>

  datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]

  searchData = int(input('찾으려는 숫자 입력: '))
  searchResultIdx = -1

  # 마지막 인덱스 뒤에 찾으려는 값을 추가한 후 검색을 시작한다.
  datas.append(searchData) # => 얘가 바로 sentinel~!!

  n = 0
  while True:

      	❗ 검색 실패와 성공을 한 번에 판단
		if datas[n] == searchData:
            if n != len(datas) - 1:
                searchResultIdx = n
            break

  		n += 1

  print(f'datas: {datas}, datas length: {len(datas)}') # sentinel이 추가되어 있음.

  if searchResultIdx < 0:
      	print(f'찾으려는 {searchData} 데이터가 없습니다.')
  else:
		print(f'search result index: [{searchResultIdx}]')
		print(f'찾으려는 숫자는 {searchResultIdx + 1}번째 데이터이다.')

🎯 이진검색

정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.

• 이진 검색은 정렬된 리스트에서만 사용할 수 있다.

• 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다.

<동작방식>

1. 자료구조를 정렬하여 중간 값을 가져온다.

2. 중간 값과 검색 값을 비교한다.
   ① 중간 값이 검색 값과 같다면 종료! (mid == key)
   ② 중간 값보다 검색 값이 크다면 중간값 기준 자료구조의 오른쪽 구간을 대상으로 탐색한다.
       (mid < key) $~\rightsquigarrow~$ high[end] = mid -1
   ③ 중간 값보다 검색 값이 작다면 중간값 기준 자료구조의 왼쪽 구간을 대상으로 탐색한다.
       (mid > key) $~\rightsquigarrow~$ low[start] = mid +1

3. 값을 찾거나 간격이 비어있을 때(high<low)까지 반복한다.

<구현>

  def binary_search(nums, key):
      low, high = 0, len(nums)-1

      ❕# 검색 성공 조건
      while low <= high:
          mid_idx = (low + high) // 2

          if key == nums[mid_idx]:
              return mid_idx
          elif key > muns[mid_idx]:
              low = mid_idx +1
          else:
              high = mid_idx -1

      ❗# 검색 실패 조건: low > high
      return -1