순차탐색/이진탐색

탐색 / 정렬 문제

탐색 알고리즘 : 여러 항목 중 특정 한가지 항목의 존재 유무를 판별하거나, 어디에 위치해 있는지 찾기 위한 방법이다.

 

 

 

순차탐색 : 순차로 데이터를 탐색한다.

이진탐색 : 반으로 쪼개면서 탐색한다.

---

순차 탐색 ( Sequential Search )

= 순차로 데이터를 탐색한다.

리스트 안에 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다.

 

 

찾을 데이터

수박

인덱스	0	1	2	3	4	5
원소	사과	포도	딸기	수박	참외	메론

수박이라는 데이터를 찾기 위해, 사과→포도→딸기 순서로 하나씩 확인해야 한다.

 

# 순차탐색 구현

def sequential_search(a,x): 
  n = len(a) 
  for i in range(0,n):
    if x==a[i]:
      return i

  # x가 리스트 a 안에 없을 경우
  return -1

리스트 a와 찾을 데이터 x 입력 받고,  n으로 리스트 a의 데이터 갯수를 받는다. 리스트 a 데이터 갯수 만큼 for문을 돌린다.

만약, 찾을 데이터 x 가 리스트 a값과 같을 때, 알맞은 인덱스를 반환한다. x가 리스트 a에 없을 경우, -1을 반환한다.

 

a = [3,6,8,13,25,37]

sequential_search(a,13)
>> 3
sequential_search(a,21)
>> -1

---

 

탐색 범위가 크다면?

데이터를 앞에서부터 순차적으로 확인하기에는 시간이 오래 걸릴듯..

 

리스트가 정렬 조차 되어있지 않다면?

각각의 데이터를 비교 연산하기 어려울듯.. 

 

---

이진 탐색 ( Binary Search )

= 반으로 쪼개면서 탐색한다. 

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

중간값과 비교하자!!!!

 

 

 

예시 ) 정렬된 리스트 중에서 값이 4인 원소를 찾아보자                                   

출처 : 이코테

탐색 범위

시작점 : 리스트의 첫번째 인덱스

중간점 : (시작점+끝점) // 2 인덱스     (소숫점 이하 버림)

끝   점 : 리스트의 마지막 인덱스

 

 

[ Step 1 ] 원소 4 < 중간값 8

 

1. 찾고자 하는 원소 4는 중간값[4]인 8보다 왼쪽에 존재한다.
2. 중간값 8 이상은 필요가 없다.
3. 끝점을 중간점의 왼쪽으로 옮긴다.

 

 

끝점[3] = 6 이 된다.  중간점은 (0+3)//2 = 1 이므로, 중간점[1] = 2가 된다.

 

[ Step 2 ] 원소 4 > 중간값 2

 

1. 찾고자 하는 원소 4는 중간값[1]인 2보다 오른쪽에 존재한다.
2. 중간값 2 이하는 필요가 없다.
3. 시작점을 중간점의 오른쪽으로 옮긴다.

 

 

시작점[2] = 4가 된다. 중간점은 (2+3)//2 = 2 이므로, 중간점[2] = 2가 된다.

 

[ Step 3 ] 원소 4 = 중간값 4

 

1. 탐색을 종료한다.

---

이진 탐색법 연산 특징

• 단계마다 탐색범위를 1/2 로 나눈다.
• 연산 횟수 y 는 log2(x) 와 같다.

x 데이터 8개 => y 횟수 3

1회 -> 4

2회 -> 2

3회 -> 1

 

x 데이터 32 =>  y 횟수 4

1회 -> 16

2회 -> 8

3회 -> 4

4회 -> 2

5회 -> 1

 

---

이진 탐색 구현

1) 재귀 함수 ver.

# 이진탐색 구현 (재귀함수)

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)
    

 

2) 반복문 ver.

# 이진탐색 구현 (반복문)

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

 

Tip

높은 난이도로 다른 알고리즘과 함께 섞여서 이용되는 경우가 많다.

코드가 복잡하고 코드량이 많아 구현하기 어려우니, 처음에는 외우는 것을 추천한다.

탐색 범위가 클 때 1,000만 단위가 넘어갈 경우 이진탐색을 떠올려보자.

 

---

 

파라메트릭 서치 (Parametric Search)

: 최적화 문제(알맞은 함수값을 찾는다)를 결정 문제 (yes/no) 로 바꾸는 기법

 

ex) 특정 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

   >> 탐색 범위를 좁혀가며 만족하는지 확인 후 알맞는 값 찾기

 

수 찾기 (백준 1920)

1920번: 수 찾기

입국 심사 (프로그래머스)

 

코딩테스트 연습 - 입국심사

 

 

 

코드 깃허브에 올려놨어용 :-)

 

---

참고자료

이것이 코딩 테스트이다

코들리 순차탐색

코들리 이분탐색