Binary Search

문제

https://leetcode.com/problems/binary-search

---

풀이

이미 정렬된 배열에서 target 을 찾는 거라면 가운데부터 시작해서 범위를 좁혀가면 된다.

만약 배열의 가운데 값과 target을 비교해서

1. target이 더 크다? -> 오른쪽 배열 확인
2. target이 더 작다? -> 왼쪽 배열 확인
3. 똑같다 ? -> 해당 인덱스 반환

그러면 한 번 코드를 작성해보자

---

재귀

우선 재귀의 방법으로 풀 수도 있다.
어차피 찾는 과정을 동일하기 때문에, 가운데 값을 찾는 search 함수를 잘 정의하면 계속 사용할 수 있다고 생각했다.

class Solution {
    static int answer = -1; //전역 변수를 계속 업데이트
    public int search(int[] nums, int target) {
        int middle = nums.length/2;
        //배열의 크기가 0인 경우는 찾을 수 없다는 것
        if (nums.length == 0) {
            answer = -1;
            return answer;
        }
        
      	//배열의 크기가 1인 경우에는 해당 값이 target과 동일하거나 아니거나 둘 중 하나 
        if (nums.length == 1) {
            if (nums[0] == target) return middle;
            else answer = -1;
            return answer;
        }
        
        //그 외에는 모두 target과 가운데 값을 확인하고 
        if (nums[middle] == target) return middle;
        
        //동일하지 않으면 범위만 변경하여 재귀를 진행한다.
        else if (nums[middle] < target) {
            int temp = search(Arrays.copyOfRange(nums, middle, nums.length), target);
            if (temp != -1) answer = temp + middle;
            //오른쪽 배열로 진행하게 되면 인덱스가 실제 인덱스가 아니게 되므로 
            //middle의 값을 더해줘야 한다.
        }
        else if (nums[middle] > target) answer = search(Arrays.copyOfRange(nums, 0, middle), target);
        return answer;
    }
}

생각보다 너무 어려운 코드가 되었고, 보기에도 불편해졌다. 😥😥
결과는 역시나

11ms

더 간단하게 풀어보자

---

범위만 바꾼 반복문

사실 이 문제를 재귀도 아닌 그저 양 끝 범위만 변경하면서 풀면 된다.

맨 처음에 말한 방법과 동일하지만 새로운 배열을 호출하는 것이 아닌
처음에 주어진 배열 내에서만 해결하는 것이다.

left = 0, right = 배열의 길이 -1
로 시작하여,

만약 가운데(middle)이 target보다 작다면 오른쪽 배열을 확인해야 하므로
left = middle+1, right = 배열의 길이 -1
가 될 것이다.

가운데(middle)이 target보다 크다면?
left = 0, right = middle-1
이 될 것이다.

이처럼 시작과 끝 인덱스만 정해놓고 진행하는 것이다.

그럼 여기서는 middle을 구하는 부분에 집중하면 된다.

• middle은 끝과 시작하는 값 사이 중 가운데
• 하지만 실제 배열에서의 인덱스를 구해야하기 때문에 시작값을 더해준다.

무슨 말이냐면 [1,2,3,4,5] 가 있을 때, 4를 구해야 한다고 생각해보자.

left = 0, right = 4

가운데 값은 index = (4-0)/2 = 2 이므로
2번째 값인 3은 4보다 작기 때문에 [4,5]를 확인해야 한다.

left = 3, right = 4

가운데 값은 index = (4-3)/2 = 0 이므로
0번째 값인 4는 4과 동일하기 때문에 인덱스를 반환한다.

하지만 우리가 확인한 최종적으로 인덱스는 0이다. 그렇지만 실제 배열에서의 인덱스 값은 3이다.

그러므로 우리는 항상 가운데 값을 구할 때 index에 left값을 붙여 구하고, 처음 주어진 배열에서 해결하는 것이다.

결국 left = 3, right = 4 일 때,

가운데 값은 index = (4-3)/2 + left = 0 + 3 이므로
[1,2,3,4,5]에서 3번째 값인 4를 꺼내는 것이다.

코드로 구현해보자.

class Solution {
    public int search(int[] nums, int target) {
        int l=0; int r=nums.length-1;

        while (l <= r){
            int middle = (r-l)/2 + l;
            if (nums[middle] == target) return middle;
            else if (nums[middle] > target) r=middle-1;
            else if (nums[middle] < target) l=middle+1;
        }
        return -1;
    }
}

전보다 훨~씬 간결해진 코드이다.

결과는?

0ms

좋은 결과를 얻을 수 있었다.
🥰