이분 탐색(Binary Search), 어떨 때 적용할까?
이분(이진) 탐색이란? 적용 연습 문제 🔗 프로그래머스, 예산 🔗 프로그래머스, 입국심사 ⍞ Reference 이분(이진) 탐색이란? 찾고자 하는 값을 검색할 때, 범위의 가운데 값을 검사하여 원하는 값이 나올 때까지 반씩 줄여나가며 찾는다. 사전을 찾을 때 그냥 한번 펼쳐서 찾는 단어가 없으면 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고 이 과정을 찾을 때까지 반복하는 것을 생각하면 된다. 속도 : O(log N) 🤖 O(log N)의 위력이 감이 잘 안 온다면, 4,294,967,296개(약 43억 개)의 원소가 있는 리스트에서 원하는 특정 값을 찾아낼 때 최악의 탐색 깊이(찾는 값이 없는 경우)는 딱 32회이다. 그러나 순차 탐색의 최악의 경우는 4,294,967,296회이다. 저게 0부터 순서대로 숫자..
2020. 5. 26.
