[Coding Test] 이코테 - 이진 탐색

1. 순차 탐색 (Sequential Search)

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

- 보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용

- 시간 복잡도 ≤ O(N)

 

📌 순차 탐색 코드

def sequential_serch(n, target, array) : 
    #각 원소를 하나씩 확인하여
    for i in range(n):
    	#현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target :
        	return i+1 #현재의 위치반환
            
 print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
 input_data = input().split()
 n = int(input_data[0]) #원소의 개수
 target = input_data[1] #찾고자 하는 문자열
 
 print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸")
 array = input().split()
 
 #순차 탐색 수행 결과 출력
 print(sequentia_search(n, target, array))

---

2. 이진 탐색 (Binary Search)

탐색하고자 하는 범위의 '시작점', '끝점', '중간점' 변수 3개를 사용하여 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 확인하는 방법

- 데이터가 정렬되어 있어야만 사용 가능

- 이진 탐색 과정

1	시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정함 - 중간점이 실수일 때는 소수점 이하를 버럼
2	중간점과 타겟을 비교 - 타겟일 경우, 탐색 종료 - 타겟이 아닌 경우, 시작점 혹은 끝점을 중간점의 이전 혹은 이후로 이동
3	변경된 범위에서 위 과정을 반복

 

📌 이진 탐색 코드 1 - 재귀함수

def binary_search(array, target, start, end):
    if start > end :
    	return None
        
    mid (start + end) // 2 
    #찾은 경우, 중간점 인덱스 반환
    if array[mid] == target:
    	return mid
    
    #중간점 > target의 경우, 왼쪽 확인 [start, mid-1]
    elif array[mid> target : 
    	return binary_search(array, target, start, mid-1)
    
    #중간점 < target의 경우, 오른쪽 확인 [mid+1, end]
    else:
    	return binary_search(array, targget, mid+1, end)
        
#n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
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)

 

📌 이진 탐색 코드 2 - 반복문

def binary_search(array, target, start, end):
    while start <= end :
    	mid = (start + end) //2
        
        #찾은 경우 중간점 인덱스 반환
        if array[mid] == target :
        	return mid
        #중간점 > target의 경우, 왼쪽 확인
        elif array[mid] > target :
        	end = mid - 1
        #중간점 < target의 경우, 오른쪽 확인
        	end = mid + 1
    return None

 

2-1. 이진 탐색 트리

이진탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조

- 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

- 이진 탐색 트리 조회 과정

1	루트 노트부터 방문, 부모 노드와 target 비교
2	target < 부모노드의 경우, 왼쪽 자식노드 방문 or target > 부모노드의 경우, 오른쪽 자식노드 방문
3	1, 2의 과정을 반복하여 target을 찾으면 탐색 종료

---

3. 빠르게 입력받기

    - 입력데이터가 많을 경우 sys 라이브러리의 readline() 함수를 이용

    ㄴ readline() 이용시 rstrip()함수로 공백 제거 必

 

📌 한 줄 입출력 코드

import sys
#하나의 문자열 데이터 입력받기
input_data = sys.stdin.readline().rstrip()
#입력받은 문자열 그대로 출력
print(input_data)