이진탐색

Chapter 7. 이진 탐색

이진 탐색이진 탐색을 사용하면 리스트 내에서 데이터를 매우 빠르게 탐색할 수 있다. 이진 탐색에 대해 알아보기 전에 가장 기본 탐색 방법인 순차 탐색에 대해 먼저 이해할 필요가 있다.순차 탐색 : 리스트 내의 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법데이터의 정렬 여부와 관계없이 가장 앞에 있는 원소부터 하나씩 확인데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하므로 시간 복잡도는 O(N)개념 정리이진 탐색배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘필요한 변수 : 시작점, 끝점, 중간점찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교단계마다 2로 나누는 것과 동일하므로 시간 복잡도는 O(logN)예시 : 값이 4인 카드 탐색시작점..