問題
原文
Given an array of integers
nums
which is sorted in ascending order, and an integertarget
, write a function to searchtarget
innums
. Iftarget
exists, then return its index. Otherwise, return-1
.You must write an algorithm with
O(log n)
runtime complexity.
Example 1:
123 Input: nums = [-1,0,3,5,9,12], target = 9Output: 4Explanation: 9 exists in nums and its index is 4Example 2:
123 Input: nums = [-1,0,3,5,9,12], target = 2Output: -1Explanation: 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と、整数targetが与えられます。
targetがnumsに含まれているか探索する関数を書いてください。
もし、targetが存在する場合は、そのインデックスを返し、そうでない場合は-1を返してください。
※正しくない可能性があります。
方針
・二分探索をそのまま実装する
解答
解答1:iterative(繰り返し)
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution: def search(self, nums: List[int], target: int) -> int: min = 0 max = len(nums) - 1 while min <= max: middle = (min + max) // 2 if target == nums[middle]: return middle elif target < nums[middle]: max = middle - 1 else: min = middle + 1 return -1 |
よく目にする方の解答
解答2:recursive(再帰)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution: def search(self, nums: List[int], target: int) -> int: start = 0 end = len(nums) - 1 return self.binary_search(nums, start, end, target) def binary_search(self, nums, start, end, target): if start > end: return -1 middle = (start + end) // 2 if target < nums[middle]: end = middle - 1 elif target > nums[middle]: start = middle + 1 else: return middle return self.binary_search(nums, start, end, target) |
時間・空間的なスコアはiterativeな解答よりも悪かった。
補足・参考・感想
参考
二分探索を再帰的に実装するコードは初めて見たので勉強になった。
再帰的なコードを書いたときの特徴やメリットデメリットは要確認
コメント