[Algorithm] 이진 검색(Binary Search)

1. 선형 검색(Linear Search)

• 배열에서 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다.
• 복잡도는 O(n)이다.

static int seqSearch(int[] arr, int n, int key) {
    int i = 0;

    while(true) {
      if(i == n) {
        return -1;
      }
      if(arr[i] == key) {
      	return i;
      }
      i++;
    }
}

1.1 보초법(Sentinel Method)

• 위의 선형 검색은 반복할 때마다 종료 조건 1과 2를 모두 판단한다. 보초법을 사용하여 반복문에서 종료 판단 횟수를 2회에서 1회로 줄일 수 있다. 

순서)

1. 검색할 값을 보초로 arr[n]에 대입한다.

2. 배열 요소를 순서대로 스캔한다.

 

static int seqSearch(int[] arr, int n, int key) {
    int i = 0;
    arr[n] = key; // 보초(sentinel) 추가 

    while(true) {
      if(arr[i] == key) {
      	break;
      }
      i++;
    }
    return i == n ? -1 : i;
}

 

2. 이진 검색(Bineary Search)

• 데이터가 이미 정렬(오름차순/내림차순)되어 있다는 것을 전제로 한다.
• 복잡도는 O(log n) 이다.

순서)

1. 검색할 범위는 배열 전체이고, 중앙 요소의 값을 찾는다.

2. 중앙값 a[pc]가 검색 대상보다 작을 때: 중앙 바로 오른쪽 인덱스를 새로운 검색 범위의 pl로 하여 뒤쪽으로 좁힌다.

3. 중앙값 a[pc]가 검색 대상보다 클 때: 중앙 바로 왼쪽 인덱스를 새로운 검색 범위의 pr로 하여 앞쪽으로 좁힌다.

4. 위 과정을 반복한다. 

public int binarySearch(int[] arr, int target) {
  int start = 0;
  int end = arr.length - 1;

  do {
    int middle = (start + end) / 2;
    if(arr[middle] == target) {
      return middle;
    } else if(arr[middle] < target) {
      start = middle + 1;
    } else (arr[middle] > target) {
      end = middle - 1;
    }
  } while(start <= end);

  return -1;
}

2.1 Arrays.binarySearch

• 자바는 이진 검색을 하는 메서드를 표준 라이브러리로 제공한다.
• 인풋으로 들어온 배열은 오름차순으로 정렬되었다고 가정한다.
• 검색에 성공한 경우, 검색 대상과 일치하는 요소의 인덱스를 반환한다.
• 검색에 실패한 경우, 배열안에 검색 대상이 있어야할 위치를 반환한다. (삽입 포인트를 x라고 할 때 반환 값은 -x -1이다.)

int[] arr = {1,2,3,4,5};
Arrays.binarySearch(arr, 2) // 2 반환
Arrays.binarySearch(arr, 6) // -6 반환