MONG 기술블로그

이진 탐색 ( Binary Search )이란 정렬된 배열에서 타겟을 빠르게 찾는 검색 알고리즘이다. 제약 조건 : 정렬된 상태의 배열에서 사용가능 장점 : 시간복잡도가 O(logN) 으로 매우 빠른 성능 보유 시간복잡도를 수치로 변경하여 설명해보면 다음과 같다. 크기 1억개인 배열에서 특정 값을 찾는 경우. ( 정렬된 경우 ) 순차 탐색 : 최악의 경우 1억번 탐색 필요 이진 탐색 : log100000000 번 탐색 필요. 대략 26번만의 탐색으로 특정 값을 찾을 수 있음 이를 Python 코드로 직접 구현하여 탐색 횟수를 비교해보자. import random # 1 - 천만 nums = [i for i in range(1, 10000001)] # 유니크한 백만개의 수를 1-천만 범위에서 리스트로 추출..