[JAVA]검색(2) - 이진 검색(Binary Search)

1. 이진 검색(Binary Search)이란?

ㆍ정렬되어 있는 데이터에서 원하는 값을 찾는 방법

ㆍ대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾음

ㆍ자료는 정렬된 상태여야 함

 

2. 검색 과정

ㆍ자료 중앙에 있는 원소를 고름

ㆍ중앙 원소의 값과 찾고자 하는 값을 비교

ㆍ찾고자 하는 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 데이터에 대해서 새로 검색하고,

크다면 자료의 오른쪽 데이터에 대해 새로 검색을 수행

ㆍ 찾고자 하는 값을 찾을 때 까지 반복

3. 이진 검색의 특징

ㆍ검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행

ㆍ자료에 삽입이나 삭제가 발생하게 되는 경우, 항상 정렬 상태로 유지하는 추가 작업이 필요

 

4. 시간복잡도

ㆍO(log n)

 

5. 코드 예제

int binarySearch (int arr[], int low, int high, int key) {
  while (low <= high) {
    int mid = low + (high-low) / 2;
    
    if (arr[mid] == key) // 종료 조건1 검색 성공.
      return mid; 
    else if (arr[mid] > key) 
      high = mid - 1;      
    else 
      low = mid + 1;
  }
  return -1 ; // 종료 조건2 (low > high) 검색 실패.
}