✅ 이진탐색이란?

• 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

• 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값을 비교하는 방식

• 선택한 중앙 값을 기준으로 찾고자하는 값보다 크다면 기준의 왼쪽 범위에서, 찾고자하는 값보다 작다면 기준의 오른쪽 범위에서 다시 중앙 값을 선택하여 반복한다.

• 한번 비교를 거칠때 탐색 범위가 반(1/2)으로 줄어든다.

✅ 동작방식

1. 위의 데이터 집합에서 8이란 데이터를 탐색하도록 가정한다. 첫번째 과정으로는 데이터 집합의 중앙 요소를 선택한다.
   

2. 두번째 과정으로는 중앙 요소의 값과 찾으려는 값을 서로 비교하게 되는데, 만약 찾으려는 값이 중앙 요소의 값보다 작다면 중앙 요소의 왼편에서 중앙 요소를 다시 택하고, 반대로 찾으려는 값이 중앙 요소의 값보다 크다면 오른편에서 중앙 요소를 다시 선택

   그리고 다시 이진 탐색(Binary Search)를 거치는 것입니다. 위의 경우에는 찾으려는 값인 8이 중앙값 7보다 크므로 중앙값 왼편에 있는 데이터와 비교할 필요가 없으므로 중앙 요소 오른편에서 중앙값을 다시 택한다.

3. 이제는 중앙값이 9이고, 다시 중앙값과 찾으려는 값을 다시 비교하게 됩니다. 찾으려는 값 8은 중앙값 9보다 작으므로 중앙값 왼편에서 데이터를 찾아야 한다. 그럼 다시 왼편에서 중앙값을 선택하고 남은 데이터 8이 중앙값으로 택해지게 되는데 찾으려는 데이터와 일치하므로 탐색을 끝마친다.

✅ 이진 탐색(Binary Search)의 성능

• 한번 비교가 이루어질때마다, 범위는 1/2로 줄어든다

• 위의 데이터 집합의 크기를 n으로 두고, 반복 횟수를 k로 둔다면 아래와 같은 수식이 만들어진다.