📒 탐색 알고리즘

📌 선형 탐색(Linear Search) : O(n)

• 첫번째 Index부터 순차적으로 탐색하는 알고리즘
• 리스트의 길이에 비례하는 시간을 소요한다.
• 최악의 경우 모든 원소를 비교해야할 수 있다.
• 장점
  a. 구현이 쉽다.
  b. Target Value가 리스트의 앞부분에 있을 경우 효율적이다.
• 단점
  a. 소요 시간이 리스트의 크기에 따라 선형적으로 증가한다.
  b. 리스트의 길이가 길거나 Target Value가 뒷부분에 있을 경우 비효율적이다.

📙 구현

def Linear_Search(List, Val):
	i = 0
    while i<len(List):
    	if List[i] == Val:
        	return i
        i += 1
    return -1

📌 이진 탐색(Binary Search) : O(log n)

• 탐색하려는 리스트가 이미 정렬된 상태일때 사용 가능
• 크기 순서대로 정렬되어 있다는 성질을 이용하는 것
• 한 번 비교가 이루어질 때마다 리스트를 반씩 줄인다.
• 장점
  a. 리스트의 크기가 커질수록 Target Value를 탐색하는데 걸리는 시간이 더 느리게 증가한다.
  b. 정렬된 리트스의 길이가 길거나 Target Value가 리스트의 중앙에 위치할 때 적용하기 좋다.
  c. 재귀를 사용하여 성능을 최적화할 수 있다.
• 단점
  a. 리스트를 정렬해야 하는 추가 단계가 필요하다.
  b. 선형 탐색과 비교하였을때 상대적으로 구현이 복잡하다.

📙 구현

def Binary_Search(List, Val):
	lower = 0
    upper = len(List) - 1
    idx = -1
    while lower <= upper:
    	middle = (lower + upper) // 2
        if List[middle] == Val:
        	idx = middle
            break
        elif List[middle] < Val:
        	lower = middle + 1
        else:
        	upper = middle - 1
    return idx