[leetcode] 704. Binary Search

문제

 

풀이

 

오름차순으로 정렬된 배열에 원하는 값을 찾는 문제이다.

 

문제 이름대로 이진 탐색을 이용해서 풀면 되는 문제다.

이진 탐색은 정렬된 리스트에서 값을 탐색하는 알고리즘이다.

아래와 같이 매번 탐색이 진행될 때마다 범위를 1/2씩 좁혀서 가면서 탐색한다. 그래서 시간 복잡도는 O(logN)이다.

 

<파이썬 알고리즘 인터뷰> p.516, 책만, 2020

배열에 원하는 값이 존재하면 원하는 값의 인덱스를 반환하고 아니면 -1을 반환하면 된다.

그래서 해당 문제의 종료 조건은 아래와 같이 구현할 수 있다.

• 원하는 값을 찾았을 때
  • return 원하는 값의 인덱스
• 왼쪽인덱스가 오른쪽 인덱스보다 큰 경우, 원하는 값이 배열에 없는 경우이다.
  • return -1

 

코드

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


        while (startIdx <= lastIdx) {
            int middleIdx = (startIdx + lastIdx) / 2;

            if (target == nums[middleIdx]) {
                return middleIdx;
            }

            if (target > nums[middleIdx]) {
                startIdx = middleIdx + 1;
            } else {
                lastIdx = middleIdx - 1;
            }

        }
        return -1;
        
    }
}

 

 

재귀로 풀면 다음과 같다.

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(0, nums.length-1,target, nums);
    }
    
    private int binarySearch(int start, int end, int target, int[] nums){      
        int mid=(start+end)/2;
        if(nums[mid] == target){
            return mid;
        }
        if(start >= end){ 
            return -1;
        }
        
        if(nums[mid] < target){
            return binarySearch(mid+1, end,target, nums);
        } else{
            return binarySearch(start, mid,target, nums);
        }
    }
}

 

 

참고 

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