20240311_704. Binary Search(LeetCode)

오늘의 TIL은 N으로 표현이라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

 

문제 설명

// 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.

 

이진 탐색이라는 문제 이름을 갖는 이 문제는 nums라고 주어지는 배열에 target이 존재하는지 찾는 문제이다.

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

 

또, 조건으로 이 알고리즘의 시간 복잡도는 O(log n)을 만족해야한다.

 

 

해결 방안

1. 문제의 이름처럼 이진 탐색으로 해결하는 방법

2. Array의 메서드를 이용하는 방법

으로 두 가지 방법으로 문제를 해결할 수 있다.

 

통과한 답안

1. 이진 탐색

public class Solution {
    public int Search(int[] nums, int target) {
        
        int left = 0;
        int right = nums.Length - 1;
        
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        
        return -1;
        
    }
}

 

이진 탐색을 이용하는 방법은 양 끝을 설정한 뒤에 target의 값을 해당하는 중간 값과 비교한 후에

이 값보다 작으면 왼쪽으로, 크면 오른쪽으로 진행하는 방식으로

각 분기점마다 target을 비교하면서 가장 가까운 값으로 진행하는 방식이다.

 

이는 문제에서 'is sorted in ascending order'라고 적혀있었으므로 바로 사용이 가능한데,

만약 sorting이 되어있지 않다면 적용하기 전에 sort를 해야된다.

 

이 방법의 장점은 nums의 모든 원소를 확인하지 않고도 target을 찾을 수 있는 점이 장점이며

문제의 조건인 O(log n)을 만족하는 풀이법이다.

 

 

 

2. Array의 메서드 사용하기

public class Solution {
    public int Search(int[] nums, int target) {

        if (nums.Contains(target))
        {
            return Array.IndexOf(nums, target);
        }
        else
        {
            return -1;
        }
        
    }
}

Array의 메서드를 사용하면 위의 이진 탐색보다 훨씬 간단하게 문제를 풀 수 있는데

 

Array의 기능인 Array.Contains(target)를 사용하여 해당하는 값을 갖고 있는지 확인한다.

(이 부분은 Array.IndexOf(nums, target) != null 을 사용할 수도 있다)

 

이후에 갖고 있다면 Array.IndexOf(array, target)을 사용하여 해당하는 값의 인덱스를 반환시킨다.

 

위의 두 메서드를 이용하는 방법은 이진 탐색과 비교해도 비슷한 성능을 가지므로 상황에 맞게 사용할 수 있다.