1. 이진(이분)탐색이 무엇이고

이진탐색이란, 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘입니다.

배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

2. 시간복잡도는 어떻게 되며 그 이유는 무엇인가요?

전체 데이터가 N이라고 하면

-> 첫 번째 탐색 후 절반만 남아 남은 갯수는 : N/2개

-> 두 번째 탐색에서 다시 절반만 남아 남은 수는 : N/2 x 1/2개

-> k 번째 탐색에서 남은 데이터 수는 (1/2)**k x N 이 됩니다.

최악의 경우에선 (1/2)**k x N=1 될때 까지 탐색하게 된다면 ,

양쪽에 2k 을 곱하여 N = 2K 되고,
K = log2N 이 된다.
최종적으로 k 는 탐색횟수로 N에 따라 시행횟수는 logN이 된다. 따라서 시간 복잡도는 O(logN)으로 나타낼 수 있다.