Binary Search(이진탐색/이분탐색)

이진탐색이란?

- 특정 데이터를 빠르게 검색할 수 있다. O(logN)

- 정렬되어 있는 배열에서 사용 가능하다.

 

구현 코드 (Java)

int binarySearch(int[] arr, int  target, int start, int end){

    //1. 이진탐색은 무조건 정렬된 배열에서 가능하다.
    Arrays.sort(arr);

    //2. 어떤 값을 기준으로 할지를 정하고, 초기값을 정한다. 
    //이 예시에서는 매개변수로  받는걸로 한다.
    int mid = 0;

    //start가 end보다 커질때까지 반복
    while(start<=end){
        mid = (start+end)/2;

        if(mid == target)    return mid;
        else if(mid<target)    start = mid+1;
        else    end = mid-1;
    }

    //start == end인 상황까지 모두 확인했는데 없는 경우
    return -1;
}

 

문제 풀때 주의할 점

• 어떤 값을 기준으로 탐색을 할지 잘 선정
• start, end값을 잘 설정
• 탐색할 배열에 값을 추가해 줘야하는지 체크 (ex. 백준 휴게소 세우기)

 

Parametic Search(매개변수 탐색)

이진탐색과  함께 많이 나오는 개념인데

사실 그냥 이진탐색에다가 아주 간단한 로직을 추가한거다

 

Binary Search에서는 mid와 target을 비교한다면

Parametric Search에서는 mid를 이용한 다른 값을 tartget과 비교한다. (ex. 백준 휴게소 세우기)

1477번: 휴게소 세우기

 

추천문제

github.com/Crush-on-IT/algorithm-study/blob/main/binary_search/README.md

Crush-on-IT/algorithm-study

추천 문제를 통해 연습해보면 좋습니다:)