알고리즘 문제풀이 - 선형검색과 보초법 & 이진탐색 (Python)

1. 선형 검색

 

선형 검색 알고리즘은 직선 모양으로 늘어선 요소의 배열에서 앞부터 순차적으로 검색을 수행한다.

 

선형 검색 알고리즘에서 종료 조건은 2가지이다.

1. 배열의 끝

2. 검색할 값을 발견

 

보초법은
배열의 마지막 요소로 검색 요소를 추가하여
반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.

 

# search 함수

def search(array, n, key):
    
    i=0
    array.append(key)
    # array의 마지막에 key를 추가
    
    while(True):
        if(array[i] == key):
            break
        i+=1
        # 마지막 요소까지 없으면 i = n으로 while문을 빠져나오게 된다.
      	
    return i if i != n else -1
	# 마지막 요소까지 검색하지 않았다면 인덱스를 반환하고 마지막 요소까지 검색했다면 -1을 반환

# main

array = [3, 5, 7, 2, 1, 9, 10, 24, 60, 26]
n = len(array)
key = int(input("찾을 값:"))

idx = search(array, n, key)

if(idx == -1):
    print("검색 실패")
else:
    print("{0}은 array[{1}]에 있습니다.".format(key, idx))

# 찾을 값:8
# 검색 실패

# 찾을 값:7
# 7은 array[2]에 있습니다.

# 찾을 값:3
# 3은 array[0]에 있습니다.

 

---

2. 이진 탐색

 

이진 탐색 알고리즘은 이미 정렬된 상태의 배열에서 선형 검색보다 빠르게 검색을 수행한다.

검색 규칙은 검색하려는 값이 중앙 값을 기준으로 작은지 큰지를 판별하는 것이다.

 

def binSearch(array, n, key):
    left = 0
    # 아직 검색하지 않은 값 중 가장 작은 값
    right = n-1
    # 아직 검색하지 않은 값 중 가장 큰 값

    point = 0
    # 검색 수행 기준점
    count = 0
    # 반복문 수행 카운터
    
    while(left <= right):
    # 가장 작은 값과 큰 값이 만날 때까지 반복 탐색
    
        count += 1
        
        point = int((right + left)/2)
        # 중간 값을 기준점으로 
        
        if(array[point] == key) :
            return point, count
            # 검색값을 찾으면 리턴

        elif(array[point] < key) :
            left = point + 1
            # 검색값을 찾지 못했고 기준값이 검색값보다 작은 경우 left index를 하나 올림
        else:
            right = point - 1
            # 검색값을 찾지 못했고 기준값이 검색값보다 큰 경우 right index를 하나 내림

    return -1, count

array = [10, 27, 38, 70, 99, 110, 130, 150, 200]
# 오름차순으로 정렬된 배열을 준비

key = int(input("찾을 값 :"))

idx, count = binSearch(array, len(array), key)
if(idx == -1):
    print("검색 실패 (반복문 수행:{0}회)".format(count))
else:
    print("{0}운 array[{1}]에 있습니다. (반복문 수행:{2}회)".format(key, idx, count))
    
    
# 찾을 값 :130
# 130운 array[6]에 있습니다. (반복문 수행:2회)
# 찾을 값 :8
# 검색 실패 (반복문 수행 : 3회)
# 찾을 값 :200
# 200운 array[8]에 있습니다. (반복문 수행:4회)