Data Structures and Algorithms (8)

Data Structure and Algorithms (8) : 이진탐색 & 순차탐색

1. 이진 탐색 (Binary Search)

이진탐색
탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

문제 ex)
1~30개의 병이 있다. 각 병의 뚜껑에는 1~100사이의 번호가 적혀있는데 이중 70이 있는지 없는지 확인하는 방법?

조건
1) 가장 적게 병을 따야함
2) 각 병뚜껑에 씌여진 번호는 낮은 번호 순으로 기입되어 있다.

분할 정복 알고리즘 (divide and conquer)
분할정복은 재귀를 많이 씀
분할 : 문제를 하나 또는 둘 이상으로 나눈다.
정복 : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고 그렇지 않다면 다시 나눈다

이진탐색에 적용
분할 : 리스트를 두 개의 서브 리스트로 나눈다
정복
1) 검색할 숫자 > 중간값 = 뒷부분의 서브리스트에서 검색할 숫자를 찾는다
2) 검색할 숫자 < 중간값 = 앞부분의 서브리스트에서 검색할 숫자를 찾는다

code

def BST(data, search):
  if len(data) == 1 and search == data[0]: 
    return True
  else:
      return False	
ㅤ 
  medium = len(data) // 2
  ㅤ 
  if search == data[medium]
    return True
  else:
    if search > data[medium]
      return BST(data[medium:], search)
    else:
      return BST(data[:medium], search)
      ㅤ 
------------------------------------------
ㅤ 
Import random
data_list = random.sample(range(100),10)
data_list
ㅤ
data_list.sort() // 정렬
ㅤ
BST(data_list, 7)

시간복잡도

n개의 리스트를 매번 2로 나누어 1이 될때까지 비교연산을 k회 진행
n X 1/2 X 1/2 … = 1
n X 1/2^k = 1
n = 2^k / log2n = k
빅 오 표기법으로 k+1이 결국 최종 시간복잡도, 결국 O(log n)

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

2. 순차 탐색 (Sequential Search)

순차탐색
데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

code

from random import *
ㅤ
rand_data_list = list()
for num in range (10):
rand_data_list.append(randint(1,100)) // 중복가능
ㅤ
------------------------------------------------
ㅤ
def sequencial(data, search):
  for index in range(len(data)):
    if data[index] == search:
      return index
    return -1
ㅤ
------------------------------------------------
ㅤ
sequencial(rand_data_list, 4)

시간복잡도
최악의 경우 리스트길이가 n일 때 n번 비교해야함

본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.