[알고리즘] 이진 검색 (Java)

참고 : Beautiful Code / 한빛미디어

이진검색 : 미리 정렬된 수들의 배열에서 대상 원소를 찾는 방법으로 간단하고 효과적인 방법이다. 그러나 까다로운 알고리즘이다.

프로그래머의 10% 정도만이 정확하게 구현했다고 한다.

이전검색이 발표된 것은 1946이었으나 버그 없는 코드는 12년 이상 걸렸다고 한다.

 

문제는 구현 언어가 고정 정밀도 산술을 채용하고 있으며 주어진 배열이 충분히 큰 상황에서는 문제를 노출한다는 것

Java에서는 ArrayIndexOutOfBoundsException예외가 발생한다.

 

아래 버그 코드에서

int mid = (low + high) /2;

가 문제. 합이 Integer.MAX_VALUE(Java에서는 2에 31승 - 1) 보다 큰 경우 위넘침에 의해 합이 음수가 됨.

 

해결책은

  int mid = low + ((high + low) / 2); //해결책 1 : 읽기 편한 코드

더 교묘한 방법은 비트 자리이동 방법(권고 방법)
   int mid = (low + high) >>> 1; //해결책 2 : 완벽한 코드, 읽기가 어렵다.(부호 없는 비트 자리 이동 방법)

 

실제 테스트시에는 버그가 발생하게 하려면 배열이 아주 커야 하기 때문에 버그가 발생하도록 하지는 않았다.

 

 public class binarySearch {

 public static void main(String[] args) {

  int a[] = {0,1,2,3,4,5,6,7,8,9};
  int t = 0;
  int fun = 0; //버그, 최적화 함수 선택
  int rtn = 0;
  
  t = 4; //검색 target 값
  fun = 0; //0, 1 선택으로 버그함수 또는 최적화함수를 선택
  if(fun == 0) //버그 발생
   rtn = buggyBinarySearch(a,t);
  else //최적화 함수
   rtn = goodBinarySearch(a,t);
  
  System.out.print("rt=" + rtn);
  
 }

 /*
  - int mid = (low + high) / 2
   버그 문장. low와 high의 합이 Integer.MAX_VALUE(Javasms 2에 31승 - 1 )보다 큰 경우 위넘침에 의해
   합은 음수가 된다.
  */
 public static int buggyBinarySearch(int[] a, int target) {
  int low = 0;
  int high = a.length - 1;
  
  while(low <= high) {
   int mid = (low + high) / 2;
   int midVal = a[mid];
   
   if(midVal < target)
    low = mid + 1;
   else if(midVal > target)
    high = mid -1;
   else
    return mid;
  }
  
  return -1;
 }
 
 public static int goodBinarySearch(int[] a, int target) {
  int low = 0;
  int high = a.length - 1;
  
  while(low <= high) {
   //int mid = low + ((high + low) / 2); //해결책 1 : 읽기 편한 코드
   int mid = (low + high) >>> 1; //해결책 2 : 완벽한 코드, 읽기가 어렵다.(부호 없는 비트 자리 이동 방법)
   int midVal = a[mid];
   
   if(midVal < target)
    low = mid + 1;
   else if(midVal > target)
    high = mid - 1;
   else
    return mid;
  }
  
  return -1; //검색 실패
 }
}