[Leetcode 아주 상세한 문제풀이] 704. Binary Search - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 704번 문제 Binary Search 다.

우선 문제를 살펴보자.

 

리트코드 704번 문제 Binary Search 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

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이 주어진다. 이때 배열 안에 있는 element들은 오름차순으로 되어있다. 배열과 더불어 target이 주어진다. 문제에서 요구하는바는 배열에서 target을 찾아 그것이 위치한 index를 리턴하라는 것이다. 문제는 매우 간단하지만 한 가지 조건이 있다. 바로 O (log n) time complexity로 해결해야 한다는 것이다.

이미 다른 포스트에서 time complexity에 대해서도 설명했듯이 O (log n)이란건 binary search를 통해 target을 찾으라는 뜻이다. 문제를 이해하는데 어렵진 않으므로 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

문제에서 요구하는 바와 같이 O (log n) time complexity로 이 문제를 해결하기 위해서는 binary search를 사해야 한다.

Binary search 알고리즘은 정렬된 배열에서 O (log n)의 time complexity로 탐색을 하는 대표적인 방식이다.

아마 대부분 한번 쯤 해보았을 게임인 1에서 100 사이의 숫자 하나를 추측하는 작업이다.

우리는 이 문제를 이미 어떻게 해결하는지 알고 있다.

처음 1과 100 사이의 절반인 50을 찍어보면 그것보다 큰지 작은지 알아본다.

만약 작다면 25 반대로 크다면 75를 찍어 다시 그것보다 큰지 작은지 알아본다.

이런 방식으로 특정 범위를 반으로 쪼개가며 숫자를 추측할 수 있다.

우리는 다음과 같은 방식으로 문제를 해결할 수 있다.

1) 두 개의 포인터 (left and right)를 만들어 left 포인터는 배열 처음에 right 포인터는 배열 마지막에 위치시킨다.

2) 배열의 가운데 지점을 찾는다. 만약 가운데 지점에 위치한 element가 target과 같다면 그것을 리턴한다.

3) 만약 target이 가운데 element보다 작다면 그 왼쪽 지점을 다시 탐색한다.

4) 반대로 target이 가운데 element보다 크다면 그 오른쪽 지점을 다시 탐색한다.

5) 이 과정을 반복하다보면 target을 찾을 수 있다.

6) 만약 target을 찾지 못하고 두 포인터가 만난다면 target이 존재하지 않는 것이다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

배열과 타겟을 입력받기 위한 함수를 정의해 준다. (line 1)

Left, right 포인터를 만들어 left 포인터는 배열의 가장 처음에 right 포인터는 배열의 가장 마지막에 위치시킨다. (line 2)

Left 포인터가 right 포인터보다 왼쪽에 위치하는한 탐색을 계속한다. (line 4)

앞서 설명했듯이 left포인터와 right 포인터의 가운데 지점을 찾아준다. (line 5)

만약 그 가운데 지점이 target과 같다면 그것이 우리가 찾고자 하는 것이므로 그것을 리턴한다. (line 6-7)

만약 그 가운데 지점이 target 보다 작다면 left 포인터를 가운데 지점 다음으로 옮겨준다. (line 8-9)

반대로 그 가운데 지점이 target 보다 크다면 right 포인터를 가운데 지점 앞으로 옮겨준다. (line 10-11)

이 과정을 left 포인터가 right 포인터보다 왼쪽에 위치하는한 계속한다.

만약 이 과정을 마쳤는데도 불구하고 target과 같은 element를 찾지 못했다면 그 element가 존재하지 않는 것이므로 -1을 리턴하고 종료한다. (line 13)

 

 

문제 풀이 코드

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
 
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return -1
 
# Test the function with the provided examples
nums1 = [-1, 0, 3, 5, 9, 12]
target1 = 9
print("Example 1 Output:", binary_search(nums1, target1))  # Output: 4
 
nums2 = [-1, 0, 3, 5, 9, 12]
target2 = 2
print("Example 2 Output:", binary_search(nums2, target2))  # Output: -1
 
 

 

 

704. Binary Search