이진 탐색

✏️ 이진 탐색 이란?

📍 기본 이론

• 이진 탐색은 data 가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘 이다.
• 대상 data 의 중앙값과 찾고자 하는 값을 비교해 data 의 크기를 절반씩 줄이면서 대상을 찾는다.
• O(logN) 의 시간 복잡도를 갖고 있다.

📍 핵심 이론

• 오름차순으로 정렬된 data 일 경우 아래의 과정을 반복하면 된다.
  • 내림차순 일경우 조건을 반대로 하면 된다.
  1. 현재 data 의 중앙값을 선택한다.
  2. 중앙값 > 타깃 data 일 때 중앙값 기준으로 왼쪽 data 를 선택힌다.
  3. 중앙값 < 타깃 data 일 땐 오른쪽을 선택한다.
  4. 중앙값 == 타깃 data 가 될 때 까지 반복한다.

✏️ 사용 방법

1. 오름차순 정렬

• 탐색할 배열을 오름차순 정렬해줘야 한다.
  • 라이브러리를 사용해 정렬을 할 경우 Collections.sort 가 가장 빠르다.

Arrays.sort = 병합 정렬 방식 ( 평균 - NlogN / 최악 - N^2 )

Collections.sort = 트리 정렬 방식 ( 최선 - 2N / 평균 NlogN )

2. 배열 중간 index 찾기

• 아래의 공식으로 찾을 수 있다.

int start = 0, end = N -1;

int mid = (start + end) / 2;

3. 타깃과 비교하기

static void binary(int start, int end) {

    // 배열안에 값이 없음
    if (target < list.get(start) && target > list.get(end)) 
        return;

    while(true) {
        // 중간 값 구하기
        int mid = (start + end) / 2;

        // 값 찾음
        if (target == list.get(mid)) break;

        // 값 없음
        else if (start == end) break;

        // 값이 더 큰 경우
        else if (target < list.get(mid)) end = mid;

        // 값이 더 작은 경우
        else if (target > list.get(mid)) start = mid + 1;
    }
}