프로그래밍/코딩테스트

[탐색] 이진 탐색(Binary Search)

코드몬스터 2023. 8. 2. 00:50
728x90

 

 

 

👉 특징

  • 데이터가 정렬되어 있는 상테에서 원하는 값을 찾아내는 알고리즘
  • 대 상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

 

👉 코드

  1. 현재 데이터셋의 중앙값(median)을 선택한다.
  2. 중앙값 > 타깃 데이터(target data)일 때, 중앙 값 기준으로 왼쪽 데이터셋을 선택한다.
  3. 중앙값 < 타깃 데이터일 때, 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
  4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.
public class test {
	
    static int[] arr;

    public static void main(String[] args) {
        arr = new int[]{5, 7, 8, 15, 20, 38, 52, 58, 77};
        binarySearch(58);
    }

    private static void binarySearch(int goal) {
        int low = 0;
        int high = arr.length - 1;

        while (high >= low) {
            int mid = (high + low) / 2;

            if (goal == arr[mid]) {
                break;
            } else (goal < arr[mid]) {
                high = mid - 1;
            } else {
                high = mid + 1;
            }
        }
    }
}