[이코테] CHAPTER 07 이진탐색- 순차 탐색, 이분탐색/이진탐색, 이진탐색트리

1. 순차 탐색( Sequential Search )

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

- 주로, 정렬되지 않는 리스트에서 데이터를 하나씩 차례대로 확인하는 방법

- 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점

- 리스트에 특정 원소가 있는 지 체크할 경우, 리스트에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드 이용할 경우

import sys
#순차 탐색
def sequentail_search(n,target,array):
    # n : 들어오는 숫자의 개수
    # target: 현재 비교하고 싶은 원소
    # array: 비교하고 싶은 list
    #하나씩 원소를 확인
    for i in range(n):
        if array[i] == target:
            return i+1 #list 안에 몇번째 숫자인지 반환

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

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다(ex. Kang Kong Yoon Kim Choi)")
array=sys.stdin.readline().split()

print(sequentail_search(n,target,array))

결과화면

데이터의 개수가 N개일 대 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)

---

2. 이진 탐색( Binary Search )

: 데이터가 정렬되어 있는 경우, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색

- 배열 내부의 데이터가 정렬되어 있어야만 사용 가능한 알고리즘

- 시작점, 끝점, 중간점으로 변수 3개 사용

 

정렬된 10개의 데이터 중에서 값이 2인 원소를 찾아보자

1. 시작점[인덱스 0]과 끝점[인덱스 9]을 확인한 후 둘 사이에 중간점을 정해서 중간점[인덱스 4]를 찾는다

( 0+9/2 = 4.5로 찾는다. 단, 중간점이 소수점일 경우에는 버림을 하므로 인덱스 4를 찾는다 )

2. 시작점[0]과 끝점[3]를 확인한 후 둘 사이에 중간점을 정해 중간점[1]을 찾는다.

3. 시작점[2]와 끝점[3]을 확인한 후 둘 사이에 중간점을 정해 중간점[2]을 찾는다

따라서 총, 3번 탐색으로 원소를 찾을 수 있습니다

 

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

(* 시간 복잡도 추가 설명 *)

 참고 자료 : https://kangworld.tistory.com/65

전체 데이터의 수가 N일 때,

1) 첫번째 탐색 후 남은 수 N/2 = N x (1/2)^1

2) 두번째 탐색 후 남은 수 N/2 x (1/2) = N x (1/2)^2

3) 세번재 탐색 후 남은 수 N/2 x (1/2) x (1/2) = N x (1/2)^3

·····

탐색 결과 남은 수가 1이 될 때까지 탐색하게 된다.

이 때, k번 탐색을 진행을 했다고 가정하면 , N x (1/2)^k =1 이 된다.

N x (1/2)^k =1  -> N = 2^k -> k = log2N 

2-1 ) 이진 탐색(재귀 함수)

import sys
#이진 탐색(재귀 함수)
def binary_search(array,target,start,end):
    # array : 리스트, target : 찾고자 하는 문자열
    # start : 시작점, end : 끝점
    if start>end:
        return None
    mid = (start+end) // 2
    #중간지점 갑이 target 값과 동일할 경우
    if array[mid]==target:
        return mid
    #(start,target,mid)
    #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽에 위치
    #binary_search 함수 호출
    #   -> end에는 mid-1 대입
    #   -> 나눈 몫이므로 mid에 // 작성
    elif target<array[mid]:
        return binary_search(array,target,start,mid-1)
    #(mid,target,end)
    # 중간점의 값이 찾고자 하는 값보다 큰 경우 왼쪽에 위치
    #start에 mid+1 대입
    else:
        return binary_search(array,target,mid+1,end)

#n(원소의 개수), target(찾고자 하는 문자열)을 입력 받기
print("원소의 개수와 찾고자하는 문자열을 입력하시오. 구분은 띄어쓰기 한 칸으로 합니다.(ex.10 2)")
n,target=list(map(int,sys.stdin.readline().split()))
#전체 원소 받기
array = list(map(int,sys.stdin.readline().split()))

result = binary_search(array,target,0,n-1)
if result==None:
    print("원소가 존재하지 않습니다")
else:
    print(result+1)

결과화면

2-2 ) 이진 탐색(for반복문 )

import sys
#이진 탐색(재귀 함수)
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(찾고자 하는 문자열)을 입력 받기
print("원소의 개수와 찾고자하는 문자열을 입력하시오. 구분은 띄어쓰기 한 칸으로 합니다.(ex.10 2)")
n,target=list(map(int,sys.stdin.readline().split()))
#전체 원소 받기
array = list(map(int,sys.stdin.readline().split()))

result = binary_search(array,target,0,n-1)
if result==None:
    print("원소가 존재하지 않습니다")
else:
    print(result+1)