Write an article about Binary Search in JavaScript in plain English for kids. The title of the article should be eye-catching and engaging to readers. Explanations should be concise, clear, and as visual as possible and visual example. Additionally, the article should include titles for each section in Markdown format.
What is Binary Search?
Have you ever wanted to find something quickly and easily? Binary Search is a way of quickly finding something in a list of items. It’s like a treasure hunt, but with numbers instead of clues!
How Does Binary Search Work?
Binary Search works by taking a list of items and dividing it in half. It then looks at the number in the middle of the list. If that number is the one we are looking for, then we have found it! But if the number is not the one we are looking for, then we divide the list in half again and look at the number in the middle. We keep doing this until we find the number we are looking for.
What Does Binary Search Look Like in Code?
Let’s say we have a list of numbers called numbers
that looks like this:
1 2 | <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">8</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">,</span> <span class="token number">14</span><span class="token punctuation">,</span> <span class="token number">16</span><span class="token punctuation">,</span> <span class="token number">18</span><span class="token punctuation">]</span> |
Here is a simple example of Binary Search written in Javascript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | <span class="token keyword">function</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span><span class="token parameter">numbers<span class="token punctuation">,</span> target</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Set the start and end of our search</span> <span class="token keyword">let</span> start <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">let</span> end <span class="token operator">=</span> numbers<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// Keep searching until we find the target</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>start <span class="token operator"><=</span> end<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Find the middle of our search</span> <span class="token keyword">let</span> middle <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span><span class="token punctuation">(</span>start <span class="token operator">+</span> end<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// Check if the middle is the target</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>numbers<span class="token punctuation">[</span>middle<span class="token punctuation">]</span> <span class="token operator">===</span> target<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> middle<span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">// If the middle is not the target, then </span> <span class="token comment">// check if it is greater or less than </span> <span class="token comment">// the target and adjust our search accordingly</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>numbers<span class="token punctuation">[</span>middle<span class="token punctuation">]</span> <span class="token operator"><</span> target<span class="token punctuation">)</span> <span class="token punctuation">{</span> start <span class="token operator">=</span> middle <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> end <span class="token operator">=</span> middle <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token comment">// If we don't find the target, then return -1</span> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
Try It Out!
Now that you know how Binary Search works, why not try it out for yourself? Here is an example of how you can use the code above to find the number 8 in our list of numbers:
1 2 3 4 5 6 7 | <span class="token keyword">let</span> numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">8</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">,</span> <span class="token number">14</span><span class="token punctuation">,</span> <span class="token number">16</span><span class="token punctuation">,</span> <span class="token number">18</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">let</span> target <span class="token operator">=</span> <span class="token number">8</span><span class="token punctuation">;</span> <span class="token keyword">let</span> index <span class="token operator">=</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span>numbers<span class="token punctuation">,</span> target<span class="token punctuation">)</span><span class="token punctuation">;</span> console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>index<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 4</span> |
As you can see, the index of the number 8 is 4. That means it is the 5th number in our list!
Other Example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | <span class="token comment">// An array of words in a dictionary, sorted alphabetically</span> <span class="token keyword">const</span> dictionaryWords <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token punctuation">{</span> index<span class="token operator">:</span> <span class="token number">1</span><span class="token punctuation">,</span> word<span class="token operator">:</span> <span class="token string">"book"</span> <span class="token punctuation">}</span><span class="token punctuation">,</span> <span class="token punctuation">{</span> index<span class="token operator">:</span> <span class="token number">3</span><span class="token punctuation">,</span> word<span class="token operator">:</span> <span class="token string">"computer"</span> <span class="token punctuation">}</span><span class="token punctuation">,</span> <span class="token punctuation">{</span> index<span class="token operator">:</span> <span class="token number">7</span><span class="token punctuation">,</span> word<span class="token operator">:</span> <span class="token string">"dictionary"</span> <span class="token punctuation">}</span><span class="token punctuation">,</span> <span class="token punctuation">{</span> index<span class="token operator">:</span> <span class="token number">9</span><span class="token punctuation">,</span> word<span class="token operator">:</span> <span class="token string">"elephant"</span> <span class="token punctuation">}</span><span class="token punctuation">,</span> <span class="token punctuation">{</span> index<span class="token operator">:</span> <span class="token number">80</span><span class="token punctuation">,</span> word<span class="token operator">:</span> <span class="token string">"flower"</span> <span class="token punctuation">}</span><span class="token punctuation">,</span> <span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">function</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span>list<span class="token punctuation">,</span> item<span class="token punctuation">,</span> <span class="token function-variable function">filterCondition</span> <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token parameter">e</span><span class="token punctuation">)</span> <span class="token operator">=></span> e<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Get the middle item of the list</span> <span class="token keyword">const</span> middle <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span>list<span class="token punctuation">.</span>length <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">const</span> middleItem <span class="token operator">=</span> <span class="token function">filterCondition</span><span class="token punctuation">(</span>list<span class="token punctuation">[</span>middle<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// If the item is the middle item, return it</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>item <span class="token operator">===</span> middleItem<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> list<span class="token punctuation">[</span>middle<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">// If the item is less than the middle item, search the first half of the list</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>item <span class="token operator"><</span> middleItem<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span>list<span class="token punctuation">.</span><span class="token function">slice</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> middle<span class="token punctuation">)</span><span class="token punctuation">,</span> item<span class="token punctuation">,</span> filterCondition<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">// If the item is greater than the middle item, search the second half of the list</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>item <span class="token operator">></span> middleItem<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span>list<span class="token punctuation">.</span><span class="token function">slice</span><span class="token punctuation">(</span>middle <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">,</span> item<span class="token punctuation">,</span> filterCondition<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">// If the item is not found, return -1</span> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">const</span> word <span class="token operator">=</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span>dictionaryWords<span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token parameter">e</span><span class="token punctuation">)</span> <span class="token operator">=></span> e<span class="token punctuation">.</span>index<span class="token punctuation">)</span><span class="token punctuation">;</span> console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>word<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// { index: 7, word: 'dictionary' }</span> |
Conclusion
Binary Search is a great way to quickly find something in a list of items. It is fast and efficient and can be used to solve many different types of problems. Now that you know how Binary Search works, why not give it a try?
And Finally
As always, I hope you enjoyed this article and learned something new.
Thank you and see you in the next articles!
If you liked this article, please give me a like and subscribe to support me. Thank you.