이진 탐색

이진 탐색은 배열 내부의 데이터가 정렬 되어 있어야만 사용할 수있는 알고리즘이다. 무작위일때 사용할수 있는 알고리즘이다. 이미 정렬되어있으면  빠르게 데이터를 찾을 수 있다는 것이 특징

이진 탐색은 위치를 나타내는 변수 3개를 사용하여 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점이다. 찾으려는 데이터를 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는데이터를 찾는게 이진 탐색이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Binary_Search{

    public static int binarySearch(int[] arr, int target, int start, int end){
        while(start <=end){
            int mid = (start+ end)/2;
            // 찾은경우 중간점 인덱스 반환
            if(arr[mid] == target) return mid;
            // 중간점의 값보다 찾고자 하는 값이 작은경우 왼쪽확인
            else if(arr[mid] > target) end = mid -1;
            // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽확인
            else start = mid +1;
        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 원소의 개수(N)와 찾고자 하는 값(target)을 입력받기
        int n = Integer.parseInt(br.readLine());
        int target = Integer.parseInt(br.readLine());

        // 전체 원소 입력 받기
        int[] arr = new int[n];
        String[] input = br.readLine().split(" ");
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(input[i]);
        }

        // 이진 탐색 수행 결과 출력
        int result = binarySearch(arr, target, 0, n - 1);
        if (result == -1) {
            System.out.println("원소가 존재하지 않습니다.");
        } else {
            System.out.println(result + 1);
        }
    }
}