자바 이진검색 코드 Binary Search

06 March 2020 - 3 mins read time
Tags: 자바 손코딩

이진검색

이진검색은 탐색 알고리즘의 하나로써 주어진 자료에서 빠르게 탐색하여 원하는 값을 찾을 수 있다. 주어진 자료를 반으로 분할하고 찾고자 하는 키 값을 기준으로 정복하는 방식을 반복하여 원하는 값을 찾는 방식이다.

조건 : 반드시 주어진 자료는 오른차순 또는 내림차순의 정렬

이진검색 버전 1 - 재귀

재귀를 활용하면 간결하게 이진검색 코드를 구현할 수 있다.

int binarySearch(int [] arr, int key, int left, int right) {
  if(false == isSorted(arr)) 
    return // 주어진 배열이 정렬되었는지 체크

  if(key < arr[0] || key > arr[arr.lenght-1]) 
    return //키값이 주어진 자료의 범위에서 벗어났을 때

  int mid = (left + right) / 2

  if(key == arr[mid]) return mid
  else if(key < arr[mid]) {
    return binarySearch(arr, key, left, mid-1)
  } else if(key > arr[mid]) {
    return binarySearch(arr, key, mid+1, right)
  }
}

전달받은 배열이 정렬되었는지 체크와 키 값의 범위를 체크하는 예외처리를 추가했다. 찾고자 하는 값을 배열의 중간값과 비교하면서 대소여부에 따라 배열의 범위를 다르게 분할하면서 원하는 인덱스 값을 찾을 수 있다.

이진검색 버전 2 - 반복문

반복문을 활용하여 이진검색 코드를 구현해 보자.

int binarySearch(int [] arr, int key, int low, int high) {
  if(false == isSorted(arr)) 
    return // 주어진 배열이 정렬되었는지 체크

  if(key < arr[0] || key > arr[arr.lenght-1]) 
    return //키값이 주어진 자료의 범위에서 벗어났을 때

  int mid = 0
  int res = -1

  while(low <= high) {
    mid = (low + high) / 2

    if(arr[mid] == key) {
      res = mid
      break;
    } else if(arr[mid] < key) {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }

  return res
}