【LeetCode】704. Binary Search 解答・解説【Python】

この記事は約2分で読めます。

 

問題

原文

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.

 

Example 1:

Example 2:

 

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(繰り返し)

よく目にする方の解答

解答2:recursive(再帰)

時間・空間的なスコアはiterativeな解答よりも悪かった。

 

補足・参考・感想

参考

二分探索を再帰的に実装するコードは初めて見たので勉強になった。

再帰的なコードを書いたときの特徴やメリットデメリットは要確認

二分探索の実装

 

前:268. Missing Number

次:3. Longest Substring Without Repeating Characters

LeetCode 解答・解説記事一覧

コメント