STL1

• 

  [Algorithm] 이분 탐색(Binary Search) 이분 탐색에 대한 내용을 정리해보려고 합니다. 이분 탐색 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법입니다. 이분 탐색을 사용해야하는 이유 ? 우리가 일반적으로 알고있는 선형 탐색의 경우에는 앞에서부터 순차적으로 탐색하기 때문에 시간 복잡도는 배열의 원소의 개수 만큼(O(n))이 됩니다. 만약 원소의 개수가 무수히도 많아진다면 굉장히 비효율적인 알고리즘이 되겠죠. 하지만 이분 탐색은 탐색 범위를 절반으로 나누어서 탐색하기 때문에 시간 복잡도는 O(log n)로 탐색이 가능합니다. 이분 탐색 동작 이분 탐색의 동작을 알아보도록 하겠습니다. 예를 들어서 배열 arr = {1, 3, 5, 7, 9, 10, 13, 15} .. Algorithm 2022. 8. 31.