Help us understand the problem. What is going on with this article?

アルゴリズム 体操1

Binary Search on Arrays

説明

ソートされた整数を保存するArrayと探してるキーが渡されて、もしそのキーがArrayの中にある場合はキーのIndexを返す。もし、そのキーが無ければ-1を返す。

キーが47で要素20個を保持するArray

Screen Shot 2019-11-30 at 0.58.23.png

Solution

Runtime Complexity: O(logn)

Memory Complexity: O(logn)

Binary Searchは、ソートされた配列内の要素のインデックスを見つけるために使用されます。 要素が存在しない場合もそれも同様に効率的に見つけることが出来ます。アルゴリズムは、各ステップで入力配列を半分に分割していきます。すべてのステップの後、探しているインデックスが見つかったかどうか、配列の半分を破棄できます。 したがって、解はO(logn)時間で計算できます。

大まかなアルゴリズムの流れ

  1. Arrayの調べる範囲である、一番小さいインデックスのlowと一番大きいインデックスのhighを決める。
  2. そのlowとhighから中間地点のmidの値を求める。
  3. もし、midのインデックスにある要素がキーと同じであればmidを返す。
  4. もし、midのインデックスにある要素よりも大きい場合はhigh = mid - 1。(lowはそのまま)
  5. もし、midのインデックスにある要素よりも小さい場合はlow = mid + 1。(highはそのまま)
  6. ただ、low が high よりも大きくなってしまったらキーは存在していないことになるので - 1を返す。

code

Screen Shot 2019-11-30 at 1.16.30.png

補足

Recursive ではなく、While loopを使うIterative の方法だと速度効率は同じですが、Space Complexity がO(1)と出来ます。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした