[이분 탐색] Day 1. Binary Search

LeetCode에 있는 study plan 중 Algorithm 1을 풀어보겠습니다.

 

첫 주제는 이분 탐색(Binary Search) 입니다.

 

이분 탐색을 간단하게 설명하자면, 정렬된 배열에서 특정한 숫자를 효율적으로 찾는 방법입니다.

[1, 2, 3, 4, 5, 6] 배열에서 4의 위치를 찾고 싶다 할 때, 가장 먼저 드는 생각은 맨처음부터 하나하나 찾아 나가는 것이죠.

이러면 O(n) 타임이 걸릴겁니다. 하지만 만약 배열의 길이가 무진장 길면?! O(n) 으로 해결이 안되는 경우가 생길 수도 있겠죠. 이럴 때 이분 탐색을 사용하면 O(log n) 타임으로 해결할 수 있습니다.

 

암튼.. 하루에 2~3 문제씩 있던데 이번엔 이분 탐색 세문제를 풀었습니다.

근데 뭐 너무너무너무 간단한 문제들이라.. 빠르게 정리해보겠습니다.

 

문제 바로가기

Binary Search - LeetCode

 

첫 문제입니다.

 

이름부터 binary search 네요. 정말 말 그대로 이분 탐색을 이용해서 target의 위치를 구하면 됩니다.

 

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(0, nums.length - 1, nums, target);
    }

    public int binarySearch(int start, int end, int[] nums, int target) {
        if (start > end) return -1;        // 종료 조건

        int mid = (start + end) / 2;

        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) {
            return binarySearch(mid + 1, end, nums, target);        // target이 큰 경우 오른쪽 탐색
        }
        else {
            return binarySearch(start, mid - 1, nums, target);        // target이 작은 경우 왼쪽 탐색
        }
    }
}

 

아주아주 간단합니다.

 

문제 바로가기

First Bad Version - LeetCode

 

두 번째 문제는 약~~~간 응용 문젭니다. 하지만 얘도 뭐 간단합니다. [1, 2, 3, ..., n] 의 버전이 있고, 그 중 k 번째 버전이 오류가 있으면 그 뒤에 있는 버전들도 오류가 있다... 그래서 첫번째 오류나는 k번째 버전을 찾아라.. 뭐 그런 문제입니다.

 

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        return binarySearch(1, n);
    }

    public int binarySearch(int start, int end) {
        if (start >= end) return start;
        int mid = start / 2 + end / 2;

        if (!isBadVersion(mid)) {
            return binarySearch(mid + 1, end);
        } else return binarySearch(start, mid);

    }
}

 

먼저 isBadVersion() 메서드를 써먹을 수 있는데, 얘가 나쁜 버전인지 여부를 반환해줍니다. 그럼 이분 탐색 메서드에서 다음 재귀함수가 탐색할 왼/오른쪽 부분을 정할 때 얘를 써먹으면 되겠죠. mid 변수가 나쁜 버전이 아니라면 그 이상의 버전이 나쁜 버전일테니 오른쪽을 탐색해줍니다.

반대로 나쁜 버전이라면? 앞쪽을 봐야겠죠. 근데 우연찮게 mid 번째 버전이 나쁜 버전 중 가장 낮은 버전일 수도 있습니다. 고로 앞쪽 범위에는 mid 도 꼭 포함시켜주어야 합니다.

 

아 참고로 인풋이 int 범위와 동일하기 때문에 mid 변수에 (start + end) / 2 를 해버리면 터져버릴지도...^^

 

문제 바로가기

Search Insert Position - LeetCode

 

세번째 문제입니다. 첫 문제랑 또오옥같은데 단 하나 다른게 만약 target이 nums 배열에 없다면 들어갈 위치를 리턴해주면 됩니다.

 

class Solution {
    public int searchInsert(int[] nums, int target) {
        return binarySearch(0, nums.length - 1, nums, target);
    }

    public int binarySearch(int start, int end, int[] nums, int target) {
        if (start > end) return start;    // 다른 부분

        int mid = (start + end) / 2;

        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) return binarySearch(mid + 1, end, nums, target);
        else return binarySearch(start, mid - 1, nums, target);
    }
}

 

첫 문제와 다른 부분이 종료 조건밖에 없습니다.

당연합니다. 첫 문제에서 target을 찾지 못했을 경우 -1을 리턴하는데, 이 문제에서는 target이 들어갈 위치를 리턴하면 되기 때문이죠.

 

 

 

Day 2는 Two Pointers 입니다. 영어로 쓰니깐 멋있네요.

그럼 20000~