[알고리즘] 탐색 알고리즘 정리

탐색 알고리즘

선형 탐색

리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘

# 선형 탐색
# 해당 element가 list에 존재하면 해당 element의 index를 리턴
def linear_search(element, array):
    for i in range(len(array)):
        if element == array[i]:
            return i
    return None

이진 탐색

이진 탐색 알고리즘은 찾을 값을 중간인덱스를 기준으로 비교해가며 인덱스를 절반씩 줄여가며 탐색한다.

이진 탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 한다.

# 이진 탐색
# 해당 element가 list에 존재하면 해당 element의 index를 리턴
def binary_search(element, array):
    start = 0
    end = len(array) - 1
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == element:
            return mid
        elif array[mid] > element:
            end = mid -1
        else:
            start = mid + 1

이진 트리 탐색

이진 트리 구조를 이용한 탐색 방법

## 이진 트리 탐색

# 주어진 배열
nameArray = ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스']

# 루트 노드 생성
node = TreeNode()
node.data = Array[0]
root = node


# 이진 탐색 트리 구현 -> 주어진 배열을 이진 탐색을 위한 트리로 만들어주는 함수
for element in Array[1:]:
    node = TreeNode()
    node.data = element
    
    current = root
    while True: # 작은 것은 left, 큰 것은 right로 할당
        if element < current.data:
            if current.left == None:
                current.left = node
                break
            current = current.left # 왼쪽에 이미 있으면 다시 비교
        else: # element > corrent.data인 경우
            if current.right == None:
                current.right = node
                break
            current = current.right # 오른쪽에 이미 있으면 다시 비교
            
findlist = ['마마무', '에스파'] # 찾을 이름
for i in findlist:
    findName = i

    current = root
    count = 0

    while True:
        count +=1
        if current.data == findName:
            print(findName, count,'번 만에 찾았다!')
            break
        elif findName < current.data:
            if current.left == None:
                print(findName, '목록에 없음..')
                break
            current = current.left
        else:
            if current.right == None:
                print('목록에 없음..')
                break
            current = current.right
            
----------------------------------
>>> 마마무 3 번 만에 찾았다!
>>> 에스파 목록에 없음..