💡 Algorithm

Algorithm - [ 이진 탐색 ]

date
Jun 23, 2023
slug
algorithm-03
author
status
Public
tags
Python
Algorithm
summary
탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘
type
Post
thumbnail
category
💡 Algorithm
updatedAt
Jul 28, 2023 07:05 AM

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
⇒ 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로, 시간 복잡도는
 

이진 탐색

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법 (내부 데이터가 정렬되어 있어야 한다)
⇒ 단계마다 2로 나누는 것과 동일하므로 연산 횟수는 에 비례한다고 할 수 있다. 따라서, 시간 복잡도는
  1. 재귀 함수로 구현한 이진 탐색
    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 = 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)
       
  1. 반복문으로 구현한 이진 탐색
    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)
 
(출처: 이것이 코딩 테스트다)