2021년 09월 10일 TIL - 이진 탐색

쟤 '반'으로 쪼개

변별력 있는 탐색 문제에서 이진 탐색이 자주 출몰한다.

이진 탐색이란

• 우선! 정렬된 리스트에서 사용 가능하다.
• 탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색 한다.
• 3가지 변수가 사용됨 : 시작점, 끝점, 중간점

직접 구현

public class Solution {

    public int binarySearch(int[] arr, int target) {
        int first = 0; // 시작점
        int last = arr.length - 1; // 끝점
        int mid; // 중간점

        while (first <= last) {
                mid = (first + last) / 2; // 중간점

                if (target == arr[mid]) return 1;

                if (target <= arr[mid]) last = mid - 1;
                else first = mid + 1;
        }
        return 0;
    }
}

Arrays 클래스 사용

Arrays.binarySearch(array, target);