탐색

리스트 내에서 데이터를 매우 빠르게 탐색하는 이진 탐색 알고리즘은 종류에 따라 상황에 맞게 사용하면 시간적&공간적 효율을 가져다 줄 수 있다.

 

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차레대로 확인하는 방법이다.

 

• 정렬되어 있지 않은 데이터에 대해서 탐색을 진행할 때 효율적이다
• 리스트 내 데이터가 아무리 많아도 시간이 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다.
• 리스트에 특정 값이 있는지 순차적으로 조사하기 체크하여 찾기 때문에 구현이 간단하다.
• 리스트 자료형의 Count() 메서드는 내부적으로 순차탐색을 통해서 수행이 된다.
• 가장 앞에 있는 원소부터 하나씩 확인하므로 시간 복잡도는 O(N)이다.

 

순차 탐색 소스코드 ( py )

def sequential_search( n, target, array):     for i in range(n) :    # 각 원소 n까지 모두 탐색           if array[i] == target:                     return  i + 1        # 인덱스 위치 반환 ( 1부터 시작) print(" 생성할 원소 개수와 찾을 문자열 입력하시오 ") input_data = input().split() n = int(input_data[0]) target = input_data[1] print("앞서 적은 원소 개수만큼 문자열을 입력하시오, 구분은 띄워쓰기") array =input.split() print(sequential_search(n, target, array)) >>> 생성할 원소 개수와 찾을 문자열 입력하시오  >>> 3 dog >>> 앞서 적은 개수만큼 문자열을 입력하시오, 구분은 띄워쓰기 >>> cat dog duck 2

 

 

 

 

 

이진 탐색

 

리스트 내부 데이터가 정렬되어 있다면 Up/Down 게임과 같이 범위를 좁혀가면서 탐색하는 방법이다.

 

• 데이터가 정렬되어 있어야 이진탐색이 가능하다.
• 찾으려는 데이터의 ( 시작점,  끝점,  중간점  ) 을 통해서 데이터의 범위를 구분짓는다.
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복해서 비교하여 알맞는 범위로 이동하면서 탐색한다.
• 탐색을 한번 진행하여 범위를 교체할 때 마다 원소의 개수가 절반씩 줄어들기 때문에 시간 복잡도는 O(logN)이다.
• 재귀함수로 구현하거나 반복문을 통해서 구현할 수 있다.

 

 

재귀함수로 구현한 이진탐색 코드 (py)

 

def binary_search(array, target, start, end):        if start  >  end:             return None        mid = (start + end) // 2   #중간점 구하기                if array[mid] == target:       # 중간점이  찾는 값일 때            retrurn mid        elif  array[mid]  >  target:    # 중간값보다 찾는값이 작을때 , 재귀할 때 시작부터 ~ 중간보다 작은값으로 재귀            return binary_search(array, target, start, mid - 1)        else:  # 반대로            return binary_search(array, target, mid + 1, end) n, target = list(map(int, input().split())) array = list(map(int, input().split())) result = binary_search(array, target, 0, n-1 ) if result == None:     print("원소가 존재하지 않음") else:     print(result + 1)

 

 

 

반복문으로 구현한 이진탐색 코드 (py)

 

def binary_search(array, target, start, end):        while  start  <=  end:                 mid = ( start + end ) // 2         if array[mid] == target:       # 중간점이  찾는 값일 때                 retrurn mid        elif  array[mid]  >  target:    # 중간값보다 찾는값이 작을때 , end를 중간값의 이전 값으로 조정함                 end = mid -1        else:  # 반대로 중간값이 작을 때 , start값을 중간값 이후 값으로 조정함                 start = mid + 1