이진 탐색

이진 탐색 알고리즘

• 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  • 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다

---

이진 탐색 동작 예시

• 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보자

• [Step 1] 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거)

• [Step 2] 시작점:0, 끝점: 3, 중간점: 1 (소수점 이하 제거)

• [Step 3] 시작점: 2, 끝점: 3, 중간점: 2 (소수점 이하 제거)

---

이진 탐색의 시간 복잡도

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log₂𝑁에 비례한다
• 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남는다
  • 2단계를 거치면 8개가량의 데이터만 남는다
  • 3단계를 거치면 4개가량의 데이터만 남는다
• 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 𝑂(log𝑁) 을 보장한다

 

 

// 이진 탐색 알고리즘
// 입력 값 : 5 3
// 입력 값 : 1 2 3 4 5
// 출력 값 : 3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    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 end = mid + 1;
        }
        return  -1;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int x = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());
        int [] arr = new int[x];

        st = new StringTokenizer(br.readLine()," ");
        for (int i = 0; i < x; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int result = binarySearch(arr, target, 0, x);
        if (result == -1) {
            System.out.println("원소가 존재하지 않습니다.");
        }
        else {
            System.out.println(result + 1);
        }

    }
}