이진 탐색

출처 : 이코테

 

순차탐색이란 
리스트 안에 있는 특정한 데이터를 찾기 위해 
앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

def sequential_search(n,target,array):

    for i in range(n):

        if array[i]== target:

            return i + 1

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")

input_data = input().split()

n = int(input_data[0])

target = input_data[1]

array = input().split()

print(sequential_search(n,target,array))

 

 

 

 

이진 탐색
반으로 쪼개면서 탐색하기
변수 3개 사용 시작점, 끝점, 중간점
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 탐색

 

#재귀함수로 구현

def binary_search(array, target, start,end):

    if start > end :

        return None

    mid = (start+end)//2

    if array[mid] ==target:

        return mid

    elif array[mid]>target:

        return binary_search(array,target,start,mid-1)

    else:

        return binary_search(array,target,mid+1,end)

   

n,target = list(map(int,input().split()))

array = list(map(int,input().split()))

result = binary_search(array,target,0,n-1)

if result ==None:

    print("원소가 존재하지 않습니다.")

else:

    print(result+1)

 

#반복문으로 구현

def binary_search(array,target,start,end):

    while start <=end:

        mid = (start +end)//2

        if array[mid] == target:

            return mid

        elif array[mid] >target:

            end = mid -1

        else:

            start = mid +1

    return None

n,target = list(map(int,input().split()))

array = list(map(int,input().split()))

result = binary_search(array,target, 0 ,n-1)

if result ==None:

    print("원소가 존재하지 않습니다.")

else:

    print(result +1)

   

 

저자분께서 어느정도 암기를 해놓으라고 하신 부분이다

반복 타이핑으로 암기하자 ㅎ

 

 

팁은

탐색 범위 2000만 넘기면 이진 탐색 고려