이진 탐색
-
[이진 탐색] 개념정리Algorithm/개념정리 2021. 11. 18. 10:25
순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 '보통 정렬되지 않은 리스트'에서 데이터를 찾아야 할 때 사용함 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점 시간 복잡도: O(N) → 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요함 이진 탐색 : 반으로 쪼개면서 탐색하기 조건: 배열 내부의 데이터가 정렬되어 있어야 함 → 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음 특징: 탐색 범위를 좁혀가며 데이터 탐색 가능함 이진 탐색은 위치를 나타내는 변수 3개를 사용함(탐색하고자 하는 범위의 시작점, 끝점, 중간점) 찾으려는 데이터와..