이진 탐색 (Binary Search)
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
단점은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.
하지만 검색이 반복될 때마다 목표값을 찾을 확률을 두 배가 되므로 속도가 빠르다.
성능
선형 탐색은 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행을 하고
이진 탐색은 정렬된 리스트에서 중간값이랑 비교해보고 반씩 제외하면서 탐색을 하는 알고리즘 이다.
➡ 배열의 길이가 증가할수록 선형 탐색과 이진 탐색의 속도 격차는 더욱 벌어진다.
알고리즘 평가는 최악의 경우 (제일 긴 시간이 드는 경우)로 따지는데
선형 탐색의 최악의 경우는 n개 전체를 봐야하는 경우 O(n)
이진 탐색의 최악의 경우는 log2 n개를 봐야 하는 경우 O(lg n)
