upper (1) 썸네일형 리스트형 [알고리즘] 이분탐색 이분탐색은 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 리스트의 모든 값을 비교하는 완전 탐색의 경우에는 O(n)의 시간 복잡도를 가지는 반면에 이분탐색은 O(logn)의 시간 복잡도를 가져 빠른 탐색이 가능하다. 이분탑색을 사용하기 위해서 필요조건이 있다. 1. 리스트의 데이터가 정렬되어야 한다. -> 정렬이 되어있지 않으면 원하는 데이터가 어느 범위에 있는 특정 짓을 수가 없기 때문이다. 2. 무작위 접근이 가능해야한다.(Random Access) -> 원하는 인덱스의 값을 얻기위해서 O(1) 접근이 불가능한 연결 리스트의 경우에는 이분탐색의 의의가 퇴색되기 때문이다. 기본적인 이분탐색의 알고리즘은 아래의 그림과 같다. 값이 포함된 범위 [left, right]에서 그 중간 값이니 mid.. 이전 1 다음
