1 minute read

문제 링크

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

문제 설명

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.

제한 사항

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

입출력 예 #1

  1. Input : nums = [-1,0,3,5,9,12], target = 9
  2. Output : 4
  3. Explanation : 9 exists in nums and its index is 4

입출력 예 #2

  1. Input : nums = [-1,0,3,5,9,12], target = 2
  2. Output : -1
  3. Explanation : 2 does not exist in nums so return -1

문제 풀이

  1. 재귀 풀이
  2. 반복 풀이
  3. 이진 검색 모듈을 이용한 풀이
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary_search(left, right):
            if left <= right:
                mid = (left + right) // 2

                if nums[mid] < target:
                    return binary_search(mid + 1, right)
                elif nums[mid] > target:
                    return binary_search(left, mid - 1)
                else : 
                    return mid
            else :
                return -1

        return binary_search(0, len(nums) - 1)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right :
            mid = (left + right) // 2

            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else :
                return mid
        return -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums, target)

        if index < len(nums) and nums[index] == target:
            return index
        else:
            return -1

Comments

You May Also Enjoy