이분 탐색

길이가 n인 1차원 배열 numArr 이 있을 때, O(log N) 의 시간복잡도를 가지는 알고리즘.

단, 이 기능을 이용하려면 검색하려는 기준값에 따라서 오름차순으로 배열 정렬이 필수적이다.

예시

public class Main{
  public static void main(String[] args){
    // 길이가 6인 무작위 값 배열 numArr 이 오름차순 정렬로 끝이났다고 전제하고, Target 값인 2를 찾아보자.
    
    int targetValue=3; // 혹은 Scanner 로 입력
    
    int start=0;
    int end=numArr.length-1;
    int center=Math.ceil((start+end)/2);
    
    
    while(true){
      if(targetValue==numArr[center]){
        System.out.printf("%d 열에 %d 이 있었습니다.",center, targetValue);
        break;
      } else if (targetValue>numArr[center]) {
      	end=center;
        System.out.print("해당 열은 비어있습니다.\n하위 값 영역을 탐색합니다.");
      	center=Math.ceil((start+end)/2);
      } else {
      	start=center;
        System.out.print("해당 열은 비어있습니다.\n상위 값 영역을 탐색합니다.");
      	center=Math.ceil((start+end)/2);
      }
  }
}