[코딩테스트]이분탐색(이진탐색)

📖이분탐색(이진탐색)

▪ 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘.
▪ 데이터가 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있음.
▪ 탐색 범위를 절반씩 좁혀가며 데이터를 탐색.
▪ 속도: O(logN)

📌이진탐색 과정

위치를 나타내는 변수 3개 사용
탐색하고자 하는 범위의 시작점, 끝점, 중간점.

▪ 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교.

📌이진탐색 트리

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

이진탐색 트리의 특징
▪ 부모 노드보다 왼쪽 자식 노드가 작다.
▪ 부모 노드보다 오른쪽 자식 노드가 크다.

-> 왼쪽 자식 노드<부모 노드<오른쪽 자식 노드

📌빠르게 입력받기

▪ 이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 넓은 편. (데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘 의심!)
▪ 입력 데이터가 많은 문제는 input()함수 대신 sys 라이브러리의 readline() 함수 이용.
▪ sys 라이브러리를 사용할 때는 한 줄 입력받고 나서 rstrip() 함수 호출 필수.

ex)

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

#입력받은 문자열 그대로 출력
print(input_data)

📒이것이 취업을 위한 코딩테스트다 with 파이썬 책을 참고하여 작성하였습니다.
https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661