binary search

이진 탐색 알고리즘

이진 탐색(Binary Search) 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 시간 복잡도는 $O(logn)$을 가진다. ✔ 이진 탐색 과정 1. 데이터 집합(배열)의 중앙 요소를 선택합니다. 중간값 : 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다. 여기서 target = 9 로 한다. 2. 중앙 요소의 값과 찾으려는 값을 서로 비교한다. 만약 찾으려는 값이 중앙 요소의 값보다 작다면 중앙 요소의 왼편에서 중앙 요소를 다시 택하고, 반대로 찾으려는 값이 중앙 요소의 값보다 크다면 오른편에서 중앙 요소를 다시 택하게 됩니다. 중앙값의 7과 비교하여 9가 더 크기 때문에 왼쪽을 지우고 오른쪽에서 중앙값을 구한다. 다시 구한 중앙값은 10이다. 3. 위의 2번을..