binary search5 [자료구조] 이진탐색 (Binary Search) 파이썬 (bisect, recursion, iteration) 일반적인 풀이방법 def solution(L, x): start, end = 0, len(L)-1 while start = low: mid = (high + low) // 2 # If element is present at the middle itself if arr[mid] == x: return mid # If element is smaller than mid, then it can only # be present in left subarray elif arr[mid] > x: return binary_search(arr, low, mid - 1, x) # Else the element can only be present in right subarray else: return binary_search.. 2021. 4. 20. [LeetCode] Arranging Coins 파이썬 (Binary Search, maximize) class Solution2(object): def arrangeCoins(self, n): """ :type n: int :rtype: int """ left, right = 1, n while left int: left, right = 0, n while left n: right = mid - 1 else: left = mid + 1 return right # need maximum value 문제를 직사각형으로 확장하면 쉽게 풀리지만 그걸 떠올리기가 쉬운지는 모르겠음. 높이(k)가 3일 경우, o x x o o x o o o 이런식으로 만들어 진다. 여기에 1열을 추가한다면 o x x x o o x x o o o x 이렇게 k * k+1의 직사각형의 면적의 절반이 n개의 코인을 위치시킬 수 있는 최.. 2021. 4. 16. [LeetCode] Guess Number Higher or Lower 파이썬 (binary search) while 문으로 해결하려 했더니 시간초과 Binary Search로 풀어야 함. # The guess API is already defined for you. # @param num, your guess # @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 # def guess(num: int) -> int: class Solution: def guessNumber(self, n: int) -> int: left, right = 1, n while left 2021. 4. 14. [LeetCode] Valid Perfect Square 파이썬 (Binary Search, +Lower Bound) 이렇게 풀어도 되지만 사실은 Binary Search 를 사용하는 것이 문제의 의도. class Solution: def isPerfectSquare(self, num: int) -> bool: sq = num ** 0.5 if sq == int(qs): return True return False Binary Search class Solution: def isPerfectSquare(self, num: int) -> bool: if num == 1: return True left, right = 1, num while left search right side start = mid + 1 else: end = mid # greater or equal to -> not -1 that normally do.. 2021. 4. 14. [LeetCode] Convert Sorted Array to Binary Tree python 파이썬 (recursion, median) 솔루션을 보기 전에는 어떤식으로 풀어야 하는지 감이 안왔다. 솔루션을 보고 나니 Binary Search 개념을 사용해서 mid 지점만 root 가 되도록 하면 되는 것이다. class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def sortToBST(nums): if len(nums) == 0: return None mid = nums[len(nums) // 2] root = TreeNode(mid) root.left = sortToBST(nums[:len(nums) // 2]) root.right = sortToBST(nums[len(nums) // 2 + 1:]) return root return sortToBST(num.. 2021. 4. 1. 이전 1 다음