[자료구조] 이진탐색

 

 

 

1️⃣   순차탐색 

---

 

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

•   보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용된다. 

•   자주 사용되는 탐색 알고리즘으로, 리스트에 특정 값의 원소가 있는지 체크할 때에도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소 개수를 세는 count 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다. 

•   가장 앞에있는 원소부터 차례로 확인해야 하기 때문에 시간 복잡도는 O(N) 이다. 

 

 

def sequential_search (n, target, array) : 
  for i in range(n) : 
    # 현재 원소가 찾고자 하는 원소와 동일한 경우 
    if array[i] == target : 
      return i + 1 # 현재의 위치 반환 

# n : 원소의 개수, target : 찾고자 하는 문자열, array : 문자열들을 담아둔 리스트

 

 

 

 

2️⃣   이진탐색 

---

 

•   배열의 내부가 이미 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 

•   위치를 나타내는 변수 3개를 사용한다. 시작점, 끝점, 중간점. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. 

•   이진 탐색은 한 번 확인할 때 마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN) 이다. 

•   재귀함수를 사용하거나 반복문을 사용해서 구현할 수 있다. 

 

•   코딩테스트에 단골로 나오는 알고리즘이라 외워두자 🔥

 

# 재귀함수

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) # end 포인트를 중간점 이전으로 옮기기 
  # 중간점의 값보다 찾고자 하는 값이 큰 경우 
  else : 
    return binary_search(array, target, mid+1, end) # start 포인트를 중간점 이후로 잡음

 

 

•   트리 자료구조 : 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다. 

 

•   이진 탐색 트리 자료구조 : 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조이다. 

↳  부모노드보다 왼쪽 자식 노드가 작다. 

↳  부모노드보다 오른쪽 자식 노드가 크다. 

 

 

•   이진 탐색은 입력 데이터가 많거나 탐색 범위가 넓을 때 자주 사용된다. 

 

# 입력 데이터가 길거나 많은 경우 수행 시간 줄이는 방법

import sys 
input_data = sys.stdin.readline().rstrip() 

print(input_data)