이진탐색이란 무엇일까

이진탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법을 말한다.
탐색범위를 반으로 줄여가면서 탐색하기에 매우 빠른 검색 속도를 가지고 있었다.
즉 시간 복잡도가 logN로 매우 효율적이다. 단 이 알고리즘을 적용하기 위해선 먼저 배열이 정렬된 후 이진 탐색을 해야한다. 

이진탐색의 알고리즘 동작 방식

1. 주어진 배열에서 중간 값을 찾습니다. (만약 배열의 길이가 짝수라면 중간에 가까운 왼쪽의 요소를 선택합니다.)
2. 중간 값과 찾고자 하는 값을 비교합니다.
   • 만약 중간 값이 찾고자 하는 값과 일치하면, 탐색이 완료되었습니다.
   • 만약 중간 값이 찾고자 하는 값보다 크다면, 오른쪽 절반의 배열을 버리고, 왼쪽 절반의 배열에서 탐색을 계속합니다.
   • 만약 중간 값이 찾고자 하는 값보다 작다면, 왼쪽 절반의 배열을 버리고, 오른쪽 절반의 배열에서 탐색을 계속합니다.
3. 찾고자 하는 값이 나올 때까지 위의 과정을 반복합니다. 탐색 범위가 더 이상 없어질 때까지 반복하여 배열의 양쪽 끝점이 교차되면 찾고자 하는 값이 배열에 없다는 것을 의미합니다.

자바 이진탐색 라이브러리

Arrays.binarySearch(배열, 찾고자 하는 값);

• 해당 메소드는 찾고자 하는 값이 있는 경우 해당 Index를 반환하고, 없으면 음수를 반환한다.
• 이진 탐색하기 전 이미 순서대로 정렬한 후 탐색해야 한다.

이진탐색 알고리즘 코드 예시

public class Main2 {

    // 이진 탐색 소스코드 구현(반복문)
    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) {
        Scanner sc = new Scanner(System.in);

        // 원소의 개수(n)와 찾고자 하는 값(target)을 입력받기 
        int n = sc.nextInt();
        int target = sc.nextInt();

        // 전체 원소 입력받기 
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

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

}

 

자바 라이브러리를 이용한 코드 예시

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

public class 특정수2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 데이터의 개수 N, 찾고자 하는 값 x 입력받기
        int n = sc.nextInt();
        int x = sc.nextInt();

        // 전체 데이터 입력받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int i = Arrays.binarySearch(arr, x); //첫수





    }
}