탐색 알고리즘

순차탐색

그냥 앞에서부터 싹 다 뒤져보면서 찾는거

some_list = [1, 2, 3, 5, 7, 9, 11, 13]
 
def sequencial_search(element, some_list):
    for i in range(len(some_list)):
        if some_list[i] == element:
            return i
    return None

이진탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 효율적인 알고리즘.
시간 복잡도 O(logN)을 보장한다.

변수 3개를 사용해서 구현한다.
- 시작점, 끝점, 중간점
만약에 찾으려는 위치가 중간점보다 크면 시작점을 중간점 + 1로 바꾼다.
만약에 찾으려는 위치가 중간점보다 작으면 끝점을 중간점 - 1로 바꾼다.
이를 반복하면서 중간점이 찾으려는 위치와 같아지면 탐색을 종료한다.

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1
    
    while start_index <= end_index:
        mid_index = (start_index + end_index) // 2
        
        if some_list[mid_index] == element:
            return mid_index
        elif some_list[mid_index] < element:
            start_index = mid_index + 1
        else:
            end_index = mid_index - 1
    
    return None
 
'''
10 7 
1 3 5 7 9 11 13 15 17 19
4
'''
n, target = list(map(int, input().split())) # 10 7
array = list(map(int, input().split())) # 
result = binary_search(target, array)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

정렬 가장 긴 팰린드롬 부분 문자열