이진 탐색

<이것이 취업을 위한 코딩 테스트다>를 읽고 정리한 내용입니다.

순차 탐색

• 가장 단순한 방법
• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
• 구현이 간단
• 가장 앞에 있는 원소부터 하나씩 확인해야 함. → 최악의 경우 O(N)

#순차 탐색

def sequential_search(n,target,array):
    
    for i in range(n): #순차탐색 레쓰고
        if array[i]==target: #찾으려는 값과 같다면
            return i+1 #그 위치 반환. (현 인덱스+1)

print('생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.')
input_data=input().split()
n=int(input_data[0])
target=input_data[1]

print('앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.')
array=input().split()
print(sequential_search(n, target, array))

이진 탐색

• 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음.
• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색함.
• 시작점, 끝점, 중간점 ((시작점+끝점)//2)
• 중간점과 target의 값이 같으면 탐색 종료
• 성공(인덱스 반환)과 실패(None)..만이 결과가 됨.
• O(logN) 👍🏻❤

1. 재귀함수로 구현

#이진 탐색

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 = 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)

2. 반복문으로 구현

#이진탐색 - 반복문 편

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 #mid 뒤에서 찾아보자

    return None

n, target = 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)

😉빠르게 입력받기 TIP!

• input() 함수는 동작 속도가 느림. → 시간 초과😵
• sys 라이브러리의 readline() 사용
• 정수를 입력받을 때는 rstrip() 안하고 int()로 감싸주기만 하면 됨.
• 문자열 입력받을 때는 rstrip()(맨 오른쪽 엔터 삭제)이나 strip() 으로 ‘\n’을 삭제해주자.

import sys
#하나의 문자열 데이터 입력받기
input_data=sys.stdin.readline().rstrip() #rstrip은 엔터 제거

#입력받은 문자열 그대로 출력
print(input_data)