[알고리즘] 순차탐색(선형탐색)

 알고리즘, 자료구조 - 순차 탐색(선형 탐색) 

 

순차 탐색이란?

 

리스트 또는 배열 안에 있는 첫 번째 자료부터 하나씩 비교하면서 원하는 데이터를 찾아가는 알고리즘이다. 데이터를 따로 조작할 필요가 없어 단순하지만 비효율적이라는 단점을 지니고 있다. 추가로 순차 탐색은 단방향으로 탐색을 수행하기 때문에 선형 탐색(Linear Search)라고도 부른다.

순차 탐색은 최악의 경우에 최대 n번의 비교를 필요로 하기에 시간 복잡도는 O(n)이 된다.

이는 데이터가 n개가 되면 그에 따른 연산 수도 n개를 따라가기 때문에 자료수가 많아질수록 연산의 속도가 느리다는 단점이 있다.

 

 

 

예제

 

# 리스트에서 특정 숫자의 위치 찾기

def search_num(a, x):
	n = len(a)
    for i in range(0, n): #리스트 a의 모든 값에 대해 반복
    	if x == a[i] : 	# 찾는 숫자와 값이 일치하면
        	return i	# 인덱스 값 반환
    
    return -1
    
a = [17, 92, 18, 33, 58]
print(search_num(a, 18)) # 2 출력
print(search_num(a, 900)) # -1 출력(해당 값이 없기에)

 

# 학생 번호를 입력시 해당하는 학생의 이름을 반환
def find_student(number, stuNo, stuName):
    num = len(stuNo)
    for i in range(0, num):
        if(stuNo[i] == number):
            return stuName[i]

    return "해당 학생은 없습니다."


stu_no = [39, 14, 67, 103]
stu_name = ["Justin", "John", "Mike", "Summer"]

print(find_student(39, stu_no, stu_name)) #출력 - "Justin"