제 5장: 정렬과 검색(7)

60. 검색이란 여러 개의 데이터 안에서 원하는 데이터를 찾아내는 것

• 검색: 여러 개의 데이터 안에서 원하는 데이터를 찾아내는 알고리즘.
  • 정렬만큼 빈번히 사용되는 중요 요소
  • 예시
    • 카드번호로 사용자 정보를 검색해 사용자가 쇼핑을 할 수 있는 지 여부를 판별
    • 진찰권의 환자 ID로 전자 의료 기록을 찾아냄
    • 키워드가 적힌 사이트들을 전세계 웹사이트 중에서 찾아내 목록을 표시
  • 검색 알고리즘의 종류
    • 순차 검색(리니어 서치)
    • 이진 검색(바이너리 서치)
    • 간단한 문자열 검색
    • KMP 알고리즘을 사용한 문자열 검색
    • BM 알고리즘을 사용한 문자열 검색

61. 처음부터 끝까지 샅샅이 데이터를 비교하는 순차 검색(리니어 서치)

• 순차 검색(리니어 서치: Linear search): 랜덤으로 나열된 데이터 열 안에서 원하는 데이터를 찾기 위해 원하는 데이터와 일치하는지 여부를 1번째 데이터부터 조사하는 방법
• N개의 데이터 중 원하는 데이터를 찾기까지 평균적으로 N/2 번 비교해야하기 때문에 많은 양의 데이터를 찾아내는 작업에 적합하지 않은 알고리즘
• 예시: 배열 DATA에 저장된 N개의 데이터에서 원하는 데이터 T를 찾아내는 순서
  • 1단계: 배열 DATA의 요소들을 가리키기 위한 첨자 I를 0으로 초기화
  • 2단계: I < N일 동안, 다음의 3단계 반복
  • 3단계: DATA[I] = T 일때 반복처리 종료 / DATA[I] ≠ T 일때 I를 1 증가
  • 4단계: I < N일 때 요소번호 I위치에서 원하는 데이터를 발견 / I = N일 경우 원하는 데이터가 발견되지 않음