[문제풀이] 06-08. 이분 검색

인프런, 자바(Java) 알고리즘 문제풀이

Sorting and Searching - 0608. 이분 검색

🗒️ 문제

🎈 나의 풀이

	private static int solution(int m, int[] arr) {
        Arrays.sort(arr);
        int a=0, b=arr.length-1;

        while(a<b) {
            if(m >= arr[(a+b)/2]) a = (a+b)/2;
            else b = (a+b)/2;
        }

        return a + 1;
    }
    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<n; i++) arr[i] = sc.nextInt();

        System.out.println(solution(m, arr));
    }

🖍️ 강의 풀이

  public int solution(int n, int m, int[] arr){
		int answer=0;
		Arrays.sort(arr);
		int lt=0, rt=n-1;
		while(lt<=rt){
			int mid=(lt+rt)/2;
			if(arr[mid]==m){
				answer=mid+1;
				break;
			}
			if(arr[mid]>m) rt=mid-1;
			else lt=mid+1;
		}
		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++) arr[i]=kb.nextInt();
		System.out.println(T.solution(n, m, arr));
	}

💬 짚어가기

이분탐색(이진 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를
탐색하는 방법이다. 시작 인덱스와 마지막 인덱스 사이 중간 인덱스 요소의 값을 내가 찾는 값 값과
비교하며 탐색한다.

✔️ 중간 인덱스에서 Target(찾는) 값 비교

• Target 값이 더 큰 경우 - 시작 인덱스의 값을 중간 인덱스 + 1로 변경
• Target 값이 더 작은 경우 - 마지막 인덱스의 값을 중간 인덱스 - 1로 변경

위 과정을 시작 인덱스가 마지막 인덱스 크기보다 작은 동안 반복하며 Target의 인덱스를 찾는다.
한번 탐색할 때 데이터의 크기가 절반으로 줄어듬으로 $O($log $n)$의 시간 복잡도를 갖는다.