binary search

binary search
각 배열이 ascending으로 sort되어 있을때, 특정한 값을 찾을때 사용하는 search방법. N까지 loop를 돌면서 모든 방법을 찾는 것O(N)에 비해서 아주 효과적인O(logn) search 알고리즘이다.
이게 얼마나 효과적이냐 하면 백만개중에서 찾아야 한다고 치면 25번 만에 원하는 값을 찾을 수 있다는 얘기다. N이 커지면 커질수록 엄청난 파워를 보여준다.

classic한 binarySearch알고리즘은 아래와 같다.
java에서는 Arrays.binarySearch 로도 제공된다.

 
int binarySearch(int key, int[] a){
 int lo = 0;
 int hi = a.length - 1;
 while (lo<=hi) {
  int mid = lo + (hi-lo)/2;
  if (a[mid] > key ) {
   hi = mid-1;
  }else if (a[mid] < key) {
   lo = mid + 1;
  }else{
   return mid;
  }
 }  
 return -1;
}

binary search에 기반한 몇가지 응용이 있다.

예를 들면,
어떤 조건(100보다 큰)을 만족하는 최소값 - 1번
어떤 조건(100보다 작은) 을 만족하는 최대값 - 2번


1번은 nnnnnnnyyyyyyy중에서 가장 작은 y를 찾는 것
2번은 yyyyyyyynnnnnnn(y는 조건 만족, n는 불만족)중에서 가장큰 y를 찾는 것

1번에서 조심해야 할것은 범위가 ny 로 좁혀졌을 경우, while 루프를 빠져나갈 수 없다는 것. 이유는 mid를 계산할때 소수점은 버리기 때문에 계속 lo(즉, n)에만 머물러 있다는 것. 따라서 이때 반올림을 위해서 +1을 해줘서 workaround 할 수 있다.

public static int binarySearchBiggestSatisfyingCondition(int lo, int hi, IValidator validator){  
 while (lo<hi) {
  // special
  int mid;
  if (hi-lo ==1) {
   mid = lo + (hi-lo+1)/2; // notice +1 added, round up. this is because
  }else{
   mid = lo + (hi-lo)/2; 
  }
   
  if (validator.validate(mid)){
   lo = mid;
  }else {
   hi = mid-1;
  }
 }
  
 if (validator.validate(lo)) {
  return lo ;
 }  
 return -1;  
}

같은 방식으로 2번은 이렇게 하면 된다. 단, 이때 1번처럼 while루프를 바져나오지 못하는 현상은 없다.

public static int binarySearchSmallestSatisfyingCondition(int lo, int hi, IValidator validator){
  while (lo<hi) {
   int mid = lo + (hi-lo)/2; // notice +1 added, round up. this is because 
   if ( validator.validate(mid) ) { // predicate function is true
    hi = mid;
   }else {
    lo = mid+1;
   }
  }
  
  if (validator.validate(lo)) {
   return lo ;
  }  
  return -1; 
  
 }

reference:

• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch