[4] Python 문제해결 - List 2 검색

검색 

: 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업

목적하는 탐색키를 가진 항목

탐색키 : 자료를 구변하여 인식할 수 있는 키

 

검색의 종류

순차검색, 이진 검색, 인덱싱

 

순차검색

일렬로 되어 있는 자료를 순서대로 검색하는 방법

List나 연결 List 등 순차구조로 구현된 자료구조에서 유용하다.

구현이 쉽지만, 검색 대상이 많은 경우 수행시간의 증가로 비효율적이다.

2가지 경우 - 정렬된 경우와 정렬되지 않은 경우

1. 정렬되지 않은 경우

1) 첫번째 원소부터 순서대로 검색대상과 키 값이 같은 원소가 있는지를 비교하여 찾음

2) 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환

3) 검색 대상을 찾지 못하면 실패함.

 

> 첫 번째 원소를 찾을 때에는 1번 비교

> 두 번째 원소를 찾을 때에는 2번 비교

따라서, 정렬되지 않은 자료에서의 순차검색은 시간 복잡도가 증가하게 된다.

 

< >

def sequentialSearch(a, n, key):

  i = 0

  while i < n and a[i] != key:

    i = i +1

  if i < n : return i 

  else : return -1

 

2. 정렬된 경우

1) 자료가 오름차순으로 정렬된 상태에서 검색을 시시한다고 가정

2) 자료를 순차적으로 검색하면서 키 값을 비교함

3) 원소의 키 값이 검색 대상의 키 값보다 크면 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료한다.

 

정렬되지 않은 경우보다 비교 회수가 반으로 줄어든다.

def sequentialSearch2 (a,n,key):

  i = 0

  while i < n and a[i] < key:

    i = i+1

 

  if i < n and a[i] == key : return i

  else : return -1

 

이진 검색

효율적인 검색 방법

자료으 ㅣ가운데 항목의 키 값과 비교하여 다음 검색의 우치ㅣ를 결정하고 검색을 계속하는 방법

> 목적 키를 찾을 떄 까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로줄여가면서 빠르게 검색을 수행한다.

이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

정렬된 데이터 n개가 있는 경우의 시간 복잡도는 순차 검색보다 적다.

 

검색 과정

1. 자료으 ㅣ중앙에 있는 원소를 선택

2. 중앙 원소의 값과 찾고자하는 목표 값을 비교

3. 목표값 < 중앙 원소값 : 자료으 ㅣ왼쪽 반에 대해서 새로 검색을 수행

   목표값 > 중앙 원소값 : 자료의 오른쪽 반에 대해서 새로 검색을 수행

4. 찾고자 하는 값을 찾을 때까지 [1~3]의 과정을 반복한다.

 

검색 범위의 시작점과 종료점을 이용

def binarySearch(a,key):

  start = 0

  end = len(a) -1

  while start <= end:

    middle = start + ( end - start) // 2

    if key == a[middle] : # 검색 성공

      return True

    elif Key < a[middle] :

      end = middle-1

    else

      start = middle +1

  return False # 검색 실패

 

재귀 함수

def binarySearch2(a,low,high,key):

  if low>high: #검색 실패

    return False

  else :

    middle = (low + high)//2

    if key == a[middle] #검색 성공

      return True

    elif key < a[middle]:

      return binarySearch2(a,low,middle-1,key)

    elif a[middle] <key:

      return binarySearch2(a,middle+1,high,key)

 

인덱스

데이터베이스에서 유래, 테이블에 대한 동작속도를 높임

룩 업 테이블등의 용어로 사용

인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블 저장에 필요한 디스크 공간보다 작다.

> 인덱스는 키- 필드만 갖고 있고 테이블의 다른 세부 항목은갖고 있지 않음

List를 사용한 인덱스

> 대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없음. 이러한 대량 데이터의 성능 저하 뭄ㄴ제를 해결하기 위해 List 인덱스를 사용할 수 있음.

 

tip 원본 데이터에 데이터가 삽입될 경우 상대적으로 크기가 작은 인덱스 List를 정렬하기 때문에 속도가 빠르다.