[LeetCode] 704. Binary Search

[LeetCode] 704. Binary Search

풀이_#1

기본적인 이분탐색 활용

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """

        def binarySearch(s,f,target,nums):
            if (s > f):
                return -1;
            mid = (s + f) // 2

            if (target == nums[mid]):
                return mid
            elif (target > nums[mid]):
                return binarySearch(mid + 1, f, target, nums)
            else:
                return binarySearch(s, mid - 1, target, nums)

        return(binarySearch(0, len(nums)-1, target, nums))

풀이_#2

인트 오버플로우를 막기 위해 mid 값 추정 방법 변경

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        n = len(nums)
        low = 0
        high = n - 1

        while (low <= high):
            mid = int(low + (high - low) // 2)

            if (nums[mid] == target):
                return mid
            elif (nums[mid] < target):
                low = mid + 1
            else:
                high = mid - 1
        return -1