이진 탐색(바이너리 서치)

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다

타깃 데이터 검색
중앙값 비교를 통한 대상 축소 방식
시간 복잡도 : O(logN)

이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘
구현 및 원리가 비교적 간단하므로 많은 코딩테스트에서 부분문제로 요구하는 영역

이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복
(내림차순이라면 조건을 반대로하여 과정을 반복)
1. 현재 데이터셋의 중앙값(mid) 을 선택한다
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다 (mid>target) high=mid-1로 만들어 준다
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다(mid<target) low=mid+1로 만들어 준다
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다. return mid

mid = low+(high-low)/2
mid = (low+high)/2
두번째 방식은 low+high값이 int값(2^31-1)의 범위보다 크다면 음수값으로 오버플로우 될 것이고 이 음수값을 2로 나누면 mid값은 음수가 되기 때문에 문제가 될 수 있다
low+high값이 범위를 넘어서는 경우 => 첫번째 방식
그렇지 않다면 두번째 방식이 연산이 간단하기 때문에 첫번째 방식보다 효율적이다

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {5, 4, 6, 1, 7, 8, 10};
        System.out.print("찾을 데이터 : ");
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();

        int low = 0;
        int high = arr.length - 1;
        int mid ;

        // 배열이 정렬되어 있어야 한다
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        while (low <= high) {
            mid = (low + high) / 2;
            if (target == arr[mid]) {
                System.out.println("찾는 데이터 : " + target);
                break;
            }else if (target > arr[mid])
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
}
// 예외처리는 하지 못했다.. 어디서 넣어줘야할지 모르겠다ㅠㅠ