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

62. 정렬된 데이터 안에서 고속 검색하는 이진 검색(바이너리 서치)

• 바이너리 서치: 검색할 데이터 열이 오름차/내림차 순으로 이미 정렬되었다면 빠르게 검색할 수 있음
• 검색할 데이터 열의 중앙값 M1을 기준점으로 만든다.
• M1의 값이 찾고자하는 Mt와 일치할 때까지 검색 범위를 좁혀간다.
• 중앙 값 M2, 그 중앙의 중앙의 중앙 값 M3 등을 T와 비교해 일치할때까지 검색 범위를 좁혀간다.
• 예시: 배열 DATA에 오름차순으로 저장된 N개의 데이터 중 원하는 데이터 T를 찾아내기
  • 1단계: 중앙위치 M ⇒ N/2로 만듬
  • 2단계: 검색범위 안 데이터 개수가 1개 이상일 경우 3~4단계 반복
  • 3단계
    • T = DATA[M]일 때 → 데이터를 찾아냈으므로 반복 중단.
    • T < DATA[M]일 때 → DATA[M] 및 DATA[M]의 오른쪽(큰 값)에 데이터 T는 절대 없으므로, 검색 범위를 M보다 왼쪽(작은값)으로 한다.
    • T > DATA[M]일 때 → DATA[M] 및 DATA[M]의 왼쪽(작은 값)에 데이터 T는 절대 없으므로, 검색 범위를 M보다 오른쪽(큰 값)으로 한다.
  • 4단계
    • T = DATA[M]일 때 → 요소 번호 M의 위치에서 원하는 데이터 발견.
    • T ≠ DATA[M]일 때 → 원하는 데이터가 발견되지 않음.

63. 주어진 문자열 안에서 원하는 문자열의 위치를 찾아내는 ‘문자열 검색’

• 문자열 안의 문자열을 검색하는 알고리즘에는 여러개의 문자로 이루어진 문자열을 대상으로 검색한다는 특징이 있다.
• 문자열 STR안에 부분 문자열 SUB가 존재하는 위치를 구하는 알고리즘(I에 부분문자열이 발견된 위치가 저장)
• 1단계: 문자열 비교 시작 위치를 저장하는 변수 I를 0으로 초기화.
• 2단계: ‘(I+SUB의 문자 길이) < STR의 문자열 길이’라면, 3~6단계를 반복한다.
• 3단계: 부분 문자열의 위치를 저장하는 변수 J를 0으로 초기화
• 4단계: J보다 SUB 문자열 길이가 길다면 4단계 반복
• 5단계
  • STR[I] ≠ SUB[J]일 경우 → 반복처리 종료
  • STR[I] = SUB[J]일 경우 → I와 J에 각각 1씩 더함
• 6단계
  • J와 SUB의 문자열 길이 동일 → I에 (I-J)를 저장하고 종료(I에 부분문자열 SUB가 발견된 위치가 저장)
  • J보다 SUB의 문자열 길이가 길다면 → I에 (I-J+1)를 저장
• 7단계: I에 -1(발견되지 않음)을 저장