[알고리즘] 분할 정복 기법 (Divide - and - Conquer) - 이진검색응용

이진 검색에서는 분할을 2부분으로 하여서 검색을 실시하였습니다.

이번엔 분할을 3부분으로 나누는 검색하는 알고리즘을 보여드리겠습니다.

자바로 작성하였습니다~

별거는 없습니다. 

private int three_search(int low,int high){

int midLeft;

int midRight;

if ( low > high ) return -1;

else{

midLeft = (int)((low*2+high)/3); // 1/3지점 선택

midRight = (int)((low+high*2)/3); // 2/3지점 선택

if ( key == value[midLeft] ){ // 키값 비교하여 같으면 인덱스 출력

return midLeft;

} else if ( key == value[midRight]){

return midRight;

} else {

if ( key < value[midLeft] ){ // 발견 못할 시 크기 비교하여 다음 것 실행

return three_search(low,midLeft - 1);

}else if ( key > value[midRight] ){

return three_search(midRight + 1,high);

}else{

return three_search(midLeft + 1, midRight - 1);

}

}

}

}

 

이 코드를 작성할때 주의점은 역시나 1/3과 2/3의 지점을 어떻게 찾느냐겠죠?
단순하 1/3지점은 "high+low/3" 이고, 2/3지점은 "(high+low)*2/3"라고하면 배열의 범위를 벚어나서 이상한 곳을
건든다는 에러가 발생할 것입니다~

수학의 내분점 공식을 응용하면 좋겠죠?~