[Python] 순차 검색

순차 검색

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

 - 가장 간단, 직관적

 - 순차구조로 구현된 자료구조에서 원하는 항목을 찾을때

 - 알고리즘 단순 구현이 쉬움, 수행시간 급격 증가 비효율적

 

검색 과정

- 첫번째 원소부터 수서대로 검색 대상과 키 값(우리가 찾는 값)이 동일한지 찾는다.

- 찾으면 그 원소의 인덱스(위치)or 값을 반환

- 자료구조 마지막까지 검색한다음 찾지 못하면 실패.

 

- 정렬되어 있지 않은 경우

- 찾고자 하는 원소의 순서에 따라 비교회수가 결정됨

 

시간 복잡도:O(n)

 

 

 

예제 문제 )

arr = [4,9,11,23,19,7]
 
key = 10
 
for i in range(len(arr)):
    if key == arr[i]:
        print(i, "에 위치 하고있음")
        break
else:
    print("못찾음.")
 
arr = [4,7,9,11,19,23]
 
for i in range(len(arr)):
    if key == arr[i]:
        print(i, " 에 위치하고 있음")
        break
    elif key < arr[i]:
        print(i, " 번째까지만 탐색해봄 이제 그만")
        break
else:
    print("못찾음")

 

def selectionSort(a) :
    for i in range(0, len(a)-1):
        min = i
        for j in range(i+1, len(a)):
            if a[min] > a[j]:
                min = j
        a[i], a[min] = a[min], a[i]
 
 
arr = [10, 15, 2, 19, 6, 14]
 
for i in range(len(arr)-1):
    min_idx = i
 
    for j in range(i+1, len(arr)):
        if arr[j] < arr[min_idx]:
            min_idx = j
 
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
    #temp = arr[i]
    #arr[i] = temp
    #temp = 0
    #과 같은 뜻
print(arr)
 
selectionSort(arr)
print(arr)