[Java] 88. 이진 탐색 예제

1. 배열 선언, 정렬, 확인

package algo;

import java.util.Arrays;

// 이진탐색 (배열)
public class BSearch {
    public static void main(String[] args) {
        // 1. 삽입 (무작위)
        int[] arr = {10, 4, 1, 2, 3};

        // 2. 정렬
        Arrays.sort(arr); // 정렬 라이브러리

        // 3. 정렬 확인
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }
}

2. 이진 탐색 노가다 코드

package algo;

import java.util.Arrays;

// 이진탐색 (배열)
public class BSearch02 {
    public static void main(String[] args) {
        // 1. 삽입 (무작위)
        int[] arr = {10, 4, 1, 2, 3, 0, 11};
        int mid = 3; // index 값

        // 2. 정렬
        Arrays.sort(arr); // 0,1,2,3,4,10,11

        // 3. 시작
        int target = 2; // 찾아야 할 값

        // 3.1라운드 0,1,2,3,4,10, 11
        if (target == arr[mid]) {
            System.out.println(target + " 찾았습니다(1라운드) : " + arr[mid]);
        }

        if (target < arr[mid]) { // 2 < 3
            mid = 1;
        }

        // 0,1,2,3,4,10, 11
        if (target > arr[mid]) { // 2 < 3
            mid = 5;
        }

        // 3.2라운드 0,1,2 (mid = 1 -> 1, target = 2)  [(0,1,2),3,4,10, 11]
        if (target == arr[mid]) {
            System.out.println(target + " 찾았습니다(2라운드) : " + arr[mid]);
        }

        if (target < arr[mid]) { // 2 < 1 false
            mid = 0;
        }

        if (target > arr[mid]) { // 2 > 1 true
            mid = 2;
        }

        // 3.3라운드 2 (mid = 2 -> 2, target = 2) // [(0,1,{2}),3,4,10, 11]
        if (target == arr[mid]) {
            System.out.println(target + " 찾았습니다(3라운드) : " + arr[mid]);
        }
    }
}

3. 이진 탐색 노가다 코드2

package algo;

import java.util.Arrays;

// 이진탐색 (배열)
public class BSearch03 {
    public static void main(String[] args) {
        // 1. 삽입 (무작위)
        int[] arr = {10, 4, 1, 2, 3, 0, 11};

        // 2. 정렬
        Arrays.sort(arr); // 0,1,2,3,4,10,11

        // 3. 시작
        int target = 11; // 찾아야 될 값
        int mid = 3; // index 값

        // 3.1 라운드  // [(0,1,2,3,4,10,11)]
        if (target == arr[mid]) {
            System.out.println(target + " 찾았습니다(1라운드) : " + arr[mid]);
        }

        if (target < arr[mid]) { // 11 < 3
            mid = 1;
        }

        if (target > arr[mid]) { // 11 > 3
            mid = 5;
        }

        // 3.2 라운드 // [0,1,2,3,(4,10,11)]
        if (target == arr[mid]) {
            System.out.println(target + " 찾았습니다(2라운드) : " + arr[mid]);
        }

        if (target < arr[mid]) { // 11 < 10
            //mid = 0;
            mid = 4;
        }

        if (target > arr[mid]) { // 11 > 10
            // mid = 2;
            mid = 6;
        }

        // 3.3 라운드 // [0,1,(2),3,4,10,11]
        if (target == arr[mid]) {
            System.out.println(target + " 찾았습니다(3라운드) : " + arr[mid]);
        }
    }
}

4. 이진 탐색 노가다 코드 샘플링

package algo;

import java.util.Arrays;

// 이진탐색 (배열)
public class BSearch05 {
    public static void main(String[] args) {
        // 1. 삽입 (무작위)
        int[] arr = {10, 4, 1, 2, 3, 0, 11};

        // 2. 정렬
        Arrays.sort(arr); // 0,1,2,3,4,10,11

        // 3. 시작
        int target = 0; // 찾아야 될 값
        int s = 0; // 0번지
        int e = arr.length - 1; // 6번지
        int midIndex; // index 값 저장 변수


        // 3.1 라운드  // [(0,1,2,3,4,10,11)]
        midIndex = s + (e - s) / 2; // midIndex = 3
        if (target == arr[midIndex]) {
            System.out.println(target + " 찾았습니다(1라운드) : " + arr[midIndex]);
        }

        // [(0,1,2,3),4,10,11]
        if (target < arr[midIndex]) { // 0 < 3 true
            e = midIndex - 1; // 2
        }
        // [0,1,2,3,(4,10,11)]
        if (target > arr[midIndex]) { // 0 > 3 false
            s = midIndex + 1; // s = 4
        }


        // 3.2 라운드 // [(0,1,2),3,4,10,11]
        midIndex = s + (e - s) / 2; // 2
        if (target == arr[midIndex]) {
            System.out.println(target + " 찾았습니다(2라운드) : " + arr[midIndex]);
        }

        if (target < arr[midIndex]) { // 0 < 2 false
            e = midIndex - 1; // 1
        }

        if (target > arr[midIndex]) { // 11 > 10 true
            s = midIndex + 1;
        }


        // 3.3 라운드 // [0,1,2,3,4,10,(11)]
        midIndex = s + (e - s) / 2; // 6
        if (target == arr[midIndex]) {
            System.out.println(target + " 찾았습니다(3라운드) : " + arr[midIndex]);
        }
    }
}

5. 이진 탐색 최종 코드

package algo;

import java.util.Arrays;

public class BSearch06 {
    public static void main(String[] args) {
        // 1. 삽입 (무작위)
        int[] arr = {10, 4, 1, 2, 3, 0, 11};

        // 2. 정렬
        Arrays.sort(arr); // 0,1,2,3,4,10,11

        // 3. 시작
        int target = 0; // 찾아야 될 값
        int s = 0; // 0번지
        int e = arr.length - 1; // 6번지
        int midIndex; // index 값 저장 변수

        // 3.1 라운드  // [(0,1,2,3,4,10,11)]
        while (true) {
            midIndex = s + (e - s) / 2;
            if (target == arr[midIndex]) {
                System.out.println(target + " 찾았습니다.");
                break;  // target을 찾았을 때 종료
            } else if (target < arr[midIndex]) {
                e = midIndex - 1;  // 왼쪽 절반 탐색
            } else {
                s = midIndex + 1;  // 오른쪽 절반 탐색
            }

            if (s > e) {  // 이 조건을 추가하여 종료 시점 설정
                System.out.println(target + " 찾을 수 없습니다.");
                break;  // 값을 찾을 수 없을 때 종료
            }
        }
    }
}