탐색

개념

--> 어떤 집합에서 원하는 것을 찾는 것

탐색 종류

1) 순차 탐색
2) 이진 탐색
3) 트리 탐색
--> 특정 데이터 위치인 index를 알려준다. 없다면 -1 반환

탐색 알고리즘 종류

1) 순차 탐색 : 검색할 데이터들이 정렬되어 있지 않은 상태일 때 사용
--> 처음부터 끝까지 차례대로 찾아보는 것 (쉽지만 비효율적)
2) 이진 탐색 : 검색할 데이터들이 정렬되어 있으면 매우 효율적
3) 트리 탐색 : 트리의 삽입, 삭제가 부담

순차 탐색, 이진 탐색 알고리즘의 원리와 구현

1. 순차 탐색

1) 정렬되지 않은 집합의 순차 탐색 원리와 구현

--> 집합의 데이터를 처음부터 찾는다.

## 클래스와 함수 선언 부분 ##
def seqSearch(ary, fData):
    pos = -1 # 못 찾았을 때 반환하는 index
    size = len(ary)
    print('## 비교한 데이터 ==> ', end = ' ')
    for i in range(size):
        print(ary[i], end = ' ')
        if ary[i] == fData:
            pos = i
            break
    print()
    return pos

2) 정렬된 집합의 순차 검색 원리와 구현

## 클래스와 함수 선언 부분 ##
def seqSearch(ary, fData):
    pos = -1
    size = len(ary)
    print('## 비교한 데이터 ==> ', end = ' ')
    for i in range(size):
        print(ary[i], end = ' ')
        if ary[i] == fData:
            pos = i
            break
        elif ary[i] > fData:
            break # 더 이상 비교하지 않는다.
    print()
    return pos

--> 순차 탐색의 시간 복잡도는 데이터의 개수인 O(n) 이다.

2. 이진 탐색

--> 전체를 반씩 잘라 내서 한쪽을 버리는 방식 사용
--> 데이터의 갯수가 반씩 남으므로 급격히 줄어든다.
--> 이진 탐색의 시간 복잡도는 O(log2n) 이다.

이진 탐색 구현

--> 첫 데이터를 시작, 마지막 데이터를 끝으로 지정
--> 중앙 데이터와 찾을 데이터를 비교
--> 작은 쪽의 데이터 절반을 다 버린다.

## 클래스와 함수 선언 부분 ##
def binSearch(ary, fData):
    pos = -1 # 없으면 반환할 index
    start = 0 # 첫 데이터
    end = len(ary)-1 # 끝 데이터
    while (start <= end):
        mid = (start + end) // 2
        if fData == ary[mid]:
            return mid
        elif fData > ary[mid]: # 기준보다 크면 작은 쪽 버리기
            start = mid + 1
        else:
        end = mid - 1
    return pos