[리트코드] 704. Binary Search - 반복분, 재귀 풀이

704. Binary Search

문제

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

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Explanation: 9 exists in nums and its index is 4

 

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

Explanation: 2 does not exist in nums so return -1

 

Constraints:

• 1 <= nums.length <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

 

문제 분석

• nums : 오름차순으로 정렬된 배열

• target : nums에서 찾고자 하는 정수

• 시간복잡도가 O(logn)이 되도록 알고리즘을 작성할 것

 

출력

target이 nums에 존재하면 해당 인덱스를 반환, 존재하지 않는다면 -1을 반환한다.

 

접근 방법

정렬된 배열이 주어지고 시간복잡도 O(logn)을 요구한다면 이진 탐색을 바로 떠올려야 한다.

 

이진 탐색이 헷갈린다면 아래 글을 참고하면 좋을 것 같다. 😀

탐색 알고리즘(Search Algorithm)

주어진 데이터 안에서 원하는 값을 찾는 알고리즘을 말하고 종류로는 선형 탐색(Linear Search, 완전탐색), 이진 탐색(Binary Search), DFS 또는 BFS 같은 비선형 탐색이 있다.

 

이진 탐색(Binary Search)

예) 전화번호부 생각하기

예전에 CS50 강의에서 강사님이 전화번호부를 손으로 찢은 게 생각나서 절대 잊어버리지 않는 알고리즘이다..

 

다시 돌아와서, 이진 탐색은 정렬된 데이터를 담은 리스트에서 원하는 값의 위치를 찾는 알고리즘이다. 여기서 전제 조건은 정렬이다.

• 시간 복잡도: O(logN)
  • 완전탐색을 했었다면, O(N)

이진 탐색 알고리즘 순서

1. 리스트의 중간값을 선택한다.
2. 중간값과 원하는 값을 비교한다.
   1. 중간값이 원하는 값인 경우
      • 알고리즘을 종료한다.
   2. 중간값이 원하는 값과 다른 경우
      • 중간값보다 원하는 값이 큰 경우 : 앞으로는 중간값보다 큰 값들을 탐색한다.
      • 중간값보다 원하는 값이 작은 경우 : 앞으로는 중간값보다 작은 값들을 탐색한다. 

이진 탐색 알고리즘 구현

반복문과 재귀, 2가지 방식으로 구현 가능하다.

 

이진 탐색 알고리즘 시간복잡도

이진 탐색은 새로운 탐색 영역을 기존 탐색 영역의 1/2로 나누는 것을 반복하여 원하는 값을 탐색하는 분할 정복(Divide-and-Conquer)의 방식을 갖고 있다. 시간복잡도는 O(logN)이다. 만약에 정렬이 되어 있지 않다면 추가해야 하는데, 정렬의 시간 복잡도는 O(nlogN)이다.

 

코드 구현

1. 반복문

실패 코드

public class BinarySearch {
    public int search(int[] nums, int target) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;

        // 중간 인덱스를 계산
        int midIndex = (leftIndex + rightIndex) / 2;

        while(leftIndex <= rightIndex){
            if(nums[midIndex] == target) {
                return midIndex;
            } else if(nums[midIndex] > target){
                rightIndex = midIndex - 1;
            } else {
                leftIndex = midIndex + 1;
            }
        }
        return -1;
    }
}

이유 : midIndex는 while 루프 내에서 계속 업데이트 되어야 한다.

 

성공 코드

public class BinarySearch {
    public int search(int[] nums, int target) {
        // leftIndex와 rightIndex 인덱스를 각각 0과 nums.length - 1로 설정
        int leftIndex = 0;
        int rightIndex = nums.length - 1;

        // leftIndex가 rightIndex보다 작거나 같을 때까지 while문을 돈다
        while(leftIndex <= rightIndex){
            // 중간 인덱스를 계산
            int midIndex = (leftIndex + rightIndex) / 2;

            // target이 중간 값과 같다면 해당 인덱스를 반환
            if(nums[midIndex] == target) {
                return midIndex;
                // target이 중간 값보다 작다면 rightIndex를 중간 인덱스보다 하나 작은 값으로 설정
            } else if(nums[midIndex] > target){
                rightIndex = midIndex - 1;
                // target이 중간 값보다 크다면 leftIndex를 중간 인덱스보다 하나 큰 값으로 설정
            } else {
                leftIndex = midIndex + 1;
            }
        }
        // target을 찾지 못한 경우 -1을 반환
        return -1;
    }
}

• 실행 시간 (Runtime): 0ms

• 메모리 사용량 (Memory): 45.66MB

 

2. 재귀

실패 코드

public class BinarySearchRecursion {
    public int search(int[] nums, int target) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;

        // 백트래킹 호출
        int result = backtracking(nums, target, leftIndex, rightIndex);
        return result;
    }

    public int backtracking(int[] nums, int target, int leftIndex, int rightIndex) {
        int midIndex = (leftIndex + rightIndex) / 2;

        if (nums[midIndex] == target) {
            return midIndex;
        }
        else if (nums[midIndex] > target) {
            return backtracking(nums, target, leftIndex, midIndex - 1);
        }
        else {
            return backtracking(nums, target, midIndex + 1, rightIndex);
        }
    }
}

이유 : 언제까지 백트래킹을 돌지 정하지 않았음 → if(leftIndex > rightIndex) return -1; → base case를 추가하자

 

성공 코드

public class BinarySearchRecursion {
    public int search(int[] nums, int target) {
        // leftIndex와 rightIndex 인덱스를 각각 0과 nums.length - 1로 설정
        int leftIndex = 0;
        int rightIndex = nums.length - 1;

        // 백트래킹 호출
        int result = backtracking(nums, target, leftIndex, rightIndex);
        return result;
    }

    public int backtracking(int[] nums, int target, int leftIndex, int rightIndex) {
        // 중간 인덱스 계산
        int midIndex = (leftIndex + rightIndex) / 2;

        // base case : leftIndex가 rightIndex보다 크면 -1 반환
        if (leftIndex > rightIndex) return -1;

        // target이 중간 값과 같으면 해당 인덱스 반환
        if (nums[midIndex] == target) {
            return midIndex;
        }
        // target이 중간 값보다 작으면 왼쪽 부분 탐색
        else if (nums[midIndex] > target) {
            return backtracking(nums, target, leftIndex, midIndex - 1);
        }
        // target이 중간 값보다 크면 오른쪽 부분 탐색
        else {
            return backtracking(nums, target, midIndex + 1, rightIndex);
        }
    }
}

• 실행 시간 (Runtime): 0ms

• 메모리 사용량 (Memory): 45.67MB

 

회고

처음에는 머리로만 생각하고 코드 구현을 했다. 그 후 직접 그려보면서 문제를 다시 보니 어디가 문제인지 바로 알 수 있었다. 아직 익숙하지 않으니 겉멋 부리지 말고 그림을 그려가며 문제를 풀도록 하자!