이분탐색이란?

이분탐색(Binary Search)

이분탐색을 하기위한 조건으로는 수열이 오름차순 혹은 내림차순으로 정리되어 있어야한다.
일반적인 선형탐색보다 빠르고 절반으로 줄여서 접근하기 때문에

시간 복잡도 : O(logN)

방법

1. startPoint와 endPoint를 설정
2. midPoint로 (startPoint+endPoint)/2 위치에 설정
3. searchPoint가 midPoint와 같은지 비교
 4.1 같다면 추출
 4.2 midPoint가 searchPoint보다 작다면 midPoint에 1을 더한후=> startPoint를 midPoint로 설정
 4.3 midPoint가 searchPoint보다 크다면 midPoint에 1을 뺀후=> endPoint를 midPoint로 설정
5. 이 과정을 반복적으로 실행하면서 searchPoint를 찾음

설명으로 이해가 안된다면 간단히 그림을 통해 설명

위와같은 그림이 있을때 수열내에서 65를 확인해보자.

이때 midPoint가 searchPoint의 값이 작다. 그렇다면 위에 설명에 따라 midPoint에 1을 더한후 => searchPoint(65)로 설정한다. => 다시 반복문을 돌고 3번 설명에 따라 searchPoint는 midPoint가 같게 되어 종료된다.

과정만 봐도 선형탐색보다 훨씬 빠르게 진행되는 것을 알 수 있다.

구현 (Recursion을 이용해 구현)

package Problem;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class 이분검색2 {

    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int arr[] = new int[N];

        for(int i=0; i<arr.length; i++){
            arr[i] = sc.nextInt();
        }

        solution(arr,M);

    }

    public static void solution(int arr[], int M){


        ArrayList<Integer> list = new ArrayList<>();
        for(int x: arr){
            list.add(x);
        }
        Collections.sort(list);

        int newArr[] = list.stream().mapToInt(Integer::intValue).toArray();

        System.out.println(binarySearch(newArr, 0, arr.length-1, M)+1);

    }

    public static int binarySearch(int arr[], int sp, int ep, int purpose){
        int middle = (sp+ep)/2;

        if(arr[middle]==purpose){
            return middle;
        }else if(arr[middle]>purpose){//중간점이 목표점보다 크다면 (목표점보다 오른쪽에 있음)
            return binarySearch(arr, sp, middle, purpose);
        }else {
            return binarySearch(arr, middle, ep, purpose);
        }

    }
}