이진탐색1 [알고리즘] 이진탐색 이진탐색 알고리즘은 정렬이 되어있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 먼저 배열의 중간값을 찾고하자는 값과 비교한다. 그리고 중간값이 찾고하자는 값보다 크다면 배열의 왼쪽, 작다면 배열의 오른쪽 부분으로 탐색 범위를 제한하여 다시 탐색한다. 탐색 단계가 진행될 때마다 탐색 범위는 반씩 줄어든다. 시간 복잡도는 빅오표기법에 따라 O(logN)과 같다. 이진탐색은 선형탐색에 비해 속도가 빠르지만 정렬이 되어 있는 데이터에만 적용할 수 있다는 단점이 있다. 예시 {1, 12, 38, 41, 60} 위와 같은 배열에서 41을 찾는다고 하자. 배열의 길이는 5이고 중간값은 3이다. 배열의 인덱스는 0부터 시작하므로 2번 인덱스의 값은 38이다. 38은 41보다 작기때문에 찾고자하는 값은 배열의 가운데 .. 2020. 8. 31. 이전 1 다음