[JAVA]이진 탐색(Binary Search)

이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 1/2씩 줄여가며 데이터를 탐색하는 방법.

* 이진 탐색을 수행할 때는 탐색 범위를 명시해야한다. 따라서 시작점과 끝점 그리고 중간점을 이용하여 탐색한다.

---

 예를 들어보자,

다음 정렬되어 있는 리스트에서 있는 5를 탐색하는 경우는 다음과 같다.

 

탐색이 성공하는 경우

중간 인덱스 값은 리스트의 길이의 1/2 값을 사용한다. 리스트의 길이가 홀수라면 1/2값에서 소수첫째자리에서 버림한 값을 사용한다.

 

다음은 리스트에 없는 값인 2를 탐색하는 경우이다.

 

탐색이 실패하는 경우

없는 값을 탐색하는 경우 더 이상 남은 항목이 없으면 탐색 실패로 -1를 리턴해준다.

 

이제 이진탐색의 코드를 확인해보자.

---

import java.util.Scanner;
 
public class Binary {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        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);
        }
    }
 
    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;
    }
}
 

---

<참조>
"이것이 취업을 위한 코딩 테스트다", "나동빈", https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5