Binary Search algorithm

Published by Igor Khrupin on

Basics

The main requirement for the binary search is: Array must be sorted.

The binary search work in the same way as searching phone number by person name in phonebook.

Or similar to searching word in the dictionary.

For example you need to find word “Mars”. What the steps people usually do:

  1. Open the dictionary in the middle and check any word
  2. If the word started from “P” then the word “Mars” located in the first part of the book.
  3. Then you divide the first part of the book and check the next word.
  4. The next word can start from “G”.
  5. In this case we need search second part of the first part of the book.

So, the range for the search becomes 2 times less every step.

The algorithm time complexity is O(log n)

See the illustration below:

Video with binary search in action

Diagrams

Loop implementation

PlantUML Syntax:<br /> @startuml</p><p>skinparam padding 10</p><p>start</p><p> repeat</p><p> :Found element between start and finish index. Middle element;</p><p> if (“Middle element<br /> equals to<br /> needed element?”) then (yes)<br /> :Search finished;<br /> :Return middle element index;<br /> stop<br /> elseif (“Start element<br /> equals to<br /> needed element?”) then (yes)<br /> :Search finished;<br /> :Return start element index;<br /> stop<br /> elseif (“Finish element<br /> equals to<br /> needed element?”) then (yes)<br /> :Search finished;<br /> :Return finish element index;<br /> stop<br /> elseif (“Middle element<br /> bigger than<br /> needed element?”) then (yes)<br /> :Finish index = Middle index – 1;<br /> elseif (“Middle element<br /> less than<br /> needed element?”) then (yes)<br /> :Start index = Middle index + 1;<br /> endif</p><p> repeat while (startIndex less than finishIndex) is (no)</p><p> :Search finished;<br /> :Return no item found result;</p><p>stop</p><p>@enduml<br />

Recursively implementation

PlantUML Syntax:<br /> @startuml</p><p>skinparam padding 10</p><p>start</p><p>:Found element between start and finish index. Middle element;</p><p>if (“Middle element<br /> equals to<br /> needed element?”) then (yes)<br /> :Search finished;<br /> :Return middle element index;<br /> stop<br /> elseif (“Start element<br /> equals to<br /> needed element?”) then (yes)<br /> :Search finished;<br /> :Return start element index;<br /> stop<br /> elseif (“Finish element<br /> equals to<br /> needed element?”) then (yes)<br /> :Search finished;<br /> :Return finish element index;<br /> stop<br /> elseif (“Middle element<br /> bigger than<br /> needed element?”) then (yes)<br /> :Recursion.<br /> Start search from start index<br /> to (middle element – 1);<br /> stop<br /> elseif (“Middle element<br /> less than<br /> needed element?”) then (yes)<br /> :Recursion.<br /> Start search from (middle element + 1)<br /> to finish Index;<br /> stop<br /> else<br /> :Search finished;<br /> :Element not found;<br /> stop<br /> endif<br /> @enduml<br />

Sample code

Below you will get a link to GitHub repo with Kotlin, Java, and Python source code

Download it from github

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.