이분 탐색

이분 탐색에 있어서, 숫자가 중복인지 아닌지 알아채는 게 중요하다.

중복이면 HashMap을 사용하고 아니면 그냥 일반적으로 풀면 된다.

 

가장 많이 하는 실수 중에 하나가 범위가 int형인지 int형을 넘어선 long형인지 잘 구분해야한다.

또한, 이분 탐색은 정렬된 상태에서 해야함을 잊지 말아야한다.

O(logN)에 특정 값을 찾을 수 있다.

 

Binary Search, Upperbound, Lowerbound 코드를 작성해보자.

 

---

 

Binary Search

처음에 while을 빠져나오는 조건에서 궁금한 점이 생겼다.

어떤 코드는 등호가 들어가고, 어떤 코드는 등호가 들어가지 않았다.

차이점은

등호가 들어가게 되면 ed = mid가 되고

등호가 들어가지 않으면 ed = mid - 1로 설정이 되있다.

 

static int binarySearch(int st, int ed, int target) {
        while (st <= ed) {
            int mid = (st + ed) / 2;
 
            if(arr[mid] == target) return mid;
            else if(arr[mid] > target)
                ed = mid - 1;
            else
                st = mid + 1;
        }
        return -1; // 탐색 실패
    }

Upperbound

upperbound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 index를 구한다.

헷갈리는 부분이 arr[mid] > target인데 여기서 등호가 들어가게 되면 lowerbound

등호가 들어가지 않게 되면 upperbound이다. 

등호가 들어가면 당연하게 마지막 값이 자기보다 크거나 같을 경우이기 떄문이다.

 

 
static int upperbound(int st, int ed, int target) {
        int rel = ed + 1; // while 문 안에서 갱신되지 못하면 size만큼 return 함.
        while (st <= ed) {
            int mid = (st + ed) / 2;
 
            if(arr[mid] > target) {
                rel = mid;
                ed = mid - 1;
            }
            else
                st = mid + 1;
        }
        return rel;
    }

Lowerbound

lowerbound는 찾고자 하는 값보다 크거나 같은 값이 처음으로 나타나는 index를 구한다.

 

static int lowerbound(int st, int ed, int target) {
        int rel = ed + 1;
 
        while (st <= ed) {
            int mid = (st + ed) / 2;
 
            if(arr[mid] >= target) {
                rel = mid;
                ed = mid - 1;
            }
            else
                st = mid + 1;
        }
        return rel;
    }

 

---

 

전체 코드

 

public class Main {
    static int arr[] = {1,3,3,4,4,5,6,7,8};
    public static void main(String[] args) throws IOException{
        System.out.println("binarySearch = " + binarySearch(0, arr.length - 1, 4));
        System.out.println("upperbound = " + upperbound(0, arr.length - 1, 3));
        System.out.println("lowerbound = " + lowerbound(0, arr.length - 1, 7));
    }
    static int binarySearch(int st, int ed, int target) {
        while (st <= ed) {
            int mid = (st + ed) / 2;
 
            if(arr[mid] == target) return mid;
            else if(arr[mid] > target)
                ed = mid - 1;
            else
                st = mid + 1;
        }
        return -1; // 탐색 실패
    }
 
    static int upperbound(int st, int ed, int target) {
        int rel = ed + 1; // while 문 안에서 갱신되지 못하면 size만큼 return 함.
        while (st <= ed) {
            int mid = (st + ed) / 2;
 
            if(arr[mid] > target) {
                rel = mid;
                ed = mid - 1;
            }
            else
                st = mid + 1;
        }
        return rel;
    }
 
    static int lowerbound(int st, int ed, int target) {
        int rel = ed + 1;
 
        while (st <= ed) {
            int mid = (st + ed) / 2;
 
            if(arr[mid] >= target) {
                rel = mid;
                ed = mid - 1;
            }
            else
                st = mid + 1;
        }
        return rel;
    }
}
 
/**
 * binarySearch = 4
 * upperbound = 3
 * lowerbound = 7
 */