정렬된 수 에서 특정 수의 위치 찾기 : binary search

• 여러 개의 수가 정렬 되었을 경우 특정 수를 찾는 방법
• 단순 반복문을 사용하면 앞에서 부터 차례로 찾아가기 때문에, 입력된 값에 따라 비교 횟수가 증가한다.
  즉 O(n)의 수행이 이루어진다.
• 정렬된 상태에서 수행 횟수를 줄이기 위해서는 binary  Search가 효율적이다.
  왜냐? 아래와 같은 상황이라고 가정하자. 
• 10개의 수의 배열이 주어진다.
  [12, 25, 31, 43, 53, 64, 78, 82, 95, 103]
• 95의 위치를 찾아보자.
  1) 단순 반복문을 사용해서 하나씩 비교하면,
     12부터 차례대로 비교해서 95와 같은지 확인해야 한다.
  2) binary search를 사용하면, 중간에 있는 값이 95보다 큰지 작은지 판단한다.
  3) 중간에 있는 값은 53이다. 따라서 이제 53이전의 숫자는 고려 대상이 아니다.
  4) 즉, [64, 78, 82, 95, 103]의 숫자만 비교하면 된다.
  5) 95와 중간에 있는 값인 82를 비교한다. 82가 더 작다!
  6) [95, 103]에서 95를 찾자.|
• 즉, 단계를 거치면서 요소의 수가 절반으로 감소했다. --> O(logN)
  10개 -> 5개

public class BinarySearchProblem {

    public static void main(String[] args) {

        int[] numbers = {12, 25, 31, 43, 53, 64, 78, 82, 95, 103};

        Scanner sc = new Scanner(System.in);

        System.out.println("숫자 배열 : " + Arrays.toString(numbers));
        System.out.println("찾을 숫자를 입력하세요");

        int x = sc.nextInt();

        int left = 0;
        int right = numbers.length-1;
        int mid = (left+right)/2;
        int temp = numbers[mid];
        boolean find = false;

        while(left <= right){
            if(temp == x){
                System.out.println(x + "을(를) 찾았습니다.");
                System.out.println("위치는 "+ (mid+1) +"입니다." );
                find = true;
                break;
            }
            else if(x < temp){
                right = mid-1;
            }
            else{
                left = mid+1;
            }
            mid = (left + right)/2;
            temp = numbers[mid];
        }


        if(find == false){
            System.out.println("입력한 값 " + x + "은 존재하지 않습니다.");
        }




    }
}

* 95를 찾는 경우

숫자 배열 : [12, 25, 31, 43, 53, 64, 78, 82, 95, 103]
찾을 숫자를 입력하세요
95
95을(를) 찾았습니다.
위치는 9입니다.

* 배열에 없는 수인 90을 찾는 경우

숫자 배열 : [12, 25, 31, 43, 53, 64, 78, 82, 95, 103]
찾을 숫자를 입력하세요
90
입력한 값 90은 존재하지 않습니다.