이진 탐색

1. 배열의 중간 요소을 기준으로 원하는 키값이랑 같은지 확인한다.
2. 중간 요소보다 키값이 크면 중간 요소와 마지막 요소의 중간 요소를 찾는다. 중간 요소보다 키값이 작으면 처음 요소와 중간 요소의 중간 요소를 찾는다.
3. 이를 start 변수와 end 변수를 이용하여 start 변수가 end보다 커지면 탐색을 종료하고 그 전에 원하는 키값을 찾으면 키값이 들어있는 배열 요소의 인덱스를 반환한다.
4. 이는 순차 탐색보다 빠르며 시간복잡도는 logN이다.
5. 이진 탐색은 배열이 무조건 정렬이 되어있어야된다.

<코드>

import java.util.Arrays;
import java.util.Scanner;

public class BinarySearchExam {
    public static int binarySearch(int[] arr, int key){
        int start = 0;
        int end = arr.length - 1;

        while(start <= end){
            int mid = (start + end) / 2;
            if (key == arr[mid]){
                return mid;
            } else if (key > arr[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("찾고자하는 정수를 입력하세요: ");
        int key = sc.nextInt();
        int[] arr = {1,3,5,33,56,2,44};
        Arrays.sort(arr); //Arrays의 sort메소드를 사용하여 정렬
        System.out.println(Arrays.toString(arr));

        int index =binarySearch(arr, key);

        if (index != -1){
            System.out.println("당신이 찾는 데이터는 " +index+"번째 인덱스에 있습니다.");
        }else {
            System.out.println("당신이 찾는 데이터가 존재하지 않습니다.");
        }
    }
}