Binary Search Algorithm Explained: Definition and Implementation
☰Fullscreen
Table of Content:
Binary search algorithm can be applied on a sorted array to search an element. Search begins with comparing middle element of array to target element. If both are equal then position of element is returned. If target element is less than middle element of array then upper half of array is discarded and again search continued by dividing the lower half. If target element is greater than middle element then lower half is discarded and search is continued in upper half.
Time Complexity
Worst Case Time Complexity: O(log n)
Best Case Time Complexity: O(1)
C program for binary search
C program for binary search: This code implements binary search in C language. It can only be used for sorted arrays, but it's fast as compared to linear search. If you wish to use binary search on an array which isn't sorted, then you must sort it using some sorting technique say merge sort and then use the binary search algorithm to find the desired element in the list. If the element to be searched is found then its position is printed. The code below assumes that the input numbers are in ascending order.
C programming code for binary search
<span class="pln"> </span><span class="com">#include</span><span class="pln"> </span><span class="str"><stdio.h></span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> c</span><span class="pun">,</span><span class="pln"> first</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">last</span><span class="pun">,</span><span class="pln"> middle</span><span class="pun">,</span><span class="pln"> n</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">,</span><span class="pln"> array</span><span class="pun">[</span><span class="lit">100</span><span class="pun">];</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Enter number of elements\n"</span><span class="pun">);</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%d"</span><span class="pun">,&</span><span class="pln">n</span><span class="pun">);</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Enter %d integers\n"</span><span class="pun">,</span><span class="pln"> n</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="pln">c </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> c </span><span class="pun"><</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> c</span><span class="pun">++)</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%d"</span><span class="pun">,&</span><span class="pln">array</span><span class="pun">[</span><span class="pln">c</span><span class="pun">]);</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Enter value to find\n"</span><span class="pun">);</span><span class="pln"> scanf</span><span class="pun">(</span><span class="str">"%d"</span><span class="pun">,</span><span class="pln"> </span><span class="pun">&</span><span class="pln">search</span><span class="pun">);</span><span class="pln"> first </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">last</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> n </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln"> middle </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="pln">first</span><span class="pun">+</span><span class="kwd">last</span><span class="pun">)/</span><span class="lit">2</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">while</span><span class="pln"> </span><span class="pun">(</span><span class="pln">first </span><span class="pun"><=</span><span class="pln"> </span><span class="kwd">last</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">array</span><span class="pun">[</span><span class="pln">middle</span><span class="pun">]</span><span class="pln"> </span><span class="pun"><</span><span class="pln"> search</span><span class="pun">)</span><span class="pln"> first </span><span class="pun">=</span><span class="pln"> middle </span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">array</span><span class="pun">[</span><span class="pln">middle</span><span class="pun">]</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> search</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"%d found at location %d.\n"</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">,</span><span class="pln"> middle</span><span class="pun">+</span><span class="lit">1</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">break</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="kwd">last</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> middle </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln"> middle </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="pln">first </span><span class="pun">+</span><span class="pln"> </span><span class="kwd">last</span><span class="pun">)/</span><span class="lit">2</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">first </span><span class="pun">></span><span class="pln"> </span><span class="kwd">last</span><span class="pun">)</span><span class="pln"> printf</span><span class="pun">(</span><span class="str">"Not found! %d isn't present in the list.\n"</span><span class="pun">,</span><span class="pln"> search</span><span class="pun">);</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> </span><span class="pun">}</span><span class="pln"> </span>
<span class="pln"> </span><span class="typ">Enter</span><span class="pln"> number </span><span class="kwd">of</span><span class="pln"> elements </span><span class="lit">10</span><span class="pln"> </span><span class="typ">Enter</span><span class="pln"> </span><span class="lit">10</span><span class="pln"> integers </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">6</span><span class="pln"> </span><span class="lit">7</span><span class="pln"> </span><span class="lit">8</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">10</span><span class="pln"> </span><span class="typ">Enter</span><span class="pln"> </span><span class="kwd">value</span><span class="pln"> to find </span><span class="lit">6</span><span class="pln"> </span><span class="lit">6</span><span class="pln"> found at location </span><span class="lit">6.</span><span class="pln"> </span><span class="typ">Press</span><span class="pln"> any key to </span><span class="kwd">continue</span><span class="pln"> </span><span class="pun">.</span><span class="pln"> </span><span class="pun">.</span><span class="pln"> </span><span class="pun">.</span><span class="pln"> </span>
Binary search is faster than linear search, but the list should be sorted, hashing is more rapid than binary search and perform searches in constant time.
Let's look at the differences in a tabular form.
| Basis of comparison | Linear search | Binary search |
|---|---|---|
| Definition | The linear search starts searching from the first element and compares each element with a searched element till the element is not found. | It finds the position of the searched element by finding the middle element of the array. |
| Sorted data | In a linear search, the elements don't need to be arranged in sorted order. | The pre-condition for the binary search is that the elements must be arranged in a sorted order. |
| Implementation | The linear search can be implemented on any linear data structure such as an array, linked list, etc. | The implementation of binary search is limited as it can be implemented only on those data structures that have two-way traversal. |
| Approach | It is based on the sequential approach. | It is based on the divide and conquer approach. |
| Size | It is preferrable for the small-sized data sets. | It is preferrable for the large-size data sets. |
| Efficiency | It is less efficient in the case of large-size data sets. | It is more efficient in the case of large-size data sets. |
| Worst-case scenario | In a linear search, the worst- case scenario for finding the element is O(n). | In a binary search, the worst-case scenario for finding the element is O(log2n). |
| Best-case scenario | In a linear search, the best-case scenario for finding the first element in the list is O(1). | In a binary search, the best-case scenario for finding the first element in the list is O(1). |
| Dimensional array | It can be implemented on both a single and multidimensional array. | It can be implemented only on a multidimensional array. |
- Question 1: How to do Binary Search in an Array?
- Question 2: Write C code to do Binary Search in an Array?
Related Questions
No Program Data.