Binary Search

Binary Search 구조

Binary Search 이분탐색이라고 부르는 알고리즘의 초기 세팅은 위 그림과 같습니다. 반드시 배열의 값이 정렬이 된 상태여야 하며 Left는 시작점 Mid는 중간점 Right는 끝점을 가르킵니다. 예시로 위 배열에서 3이라는 값의 인덱스 값을 찾아보겠습니다.

 

1. arr[Mid] >= Data 

Mid의 오른쪽 인덱스 중에서는 원하는 값이 없다는 의미이므로 기존 Right를 Mid 위치로 옮기고 Mid를 (Left + Right) / 2로 설정합니다.

2. arr[Mid] < Data 

Mid의 왼쪽 인덱스 중에서는 원하는 값이 없다는 의미이므로 기존 Left를 Mid  + 1 위치로 옮기고 Mid를 (Left + Right) / 2로 설정합니다.

Binary Search 코드

int arr[10];
int n = 10;
for (int i = 0; i < 10; i++) {
    arr[i] = i + 1;
}

int data = 3;
int left = 0, right = n;
while (left < right) {
    int mid = (left + right);
    if (arr[mid] >= data) {
        right = mid;
    }
    else {
        left = mid + 1;
    }
}

시간 복잡도는 정렬할때 O(NlogN)와 이분탐색 할때 O(logN) 입니다.