Introduction to Binary Search Algorithm

<h1>Binary Search Algorithm</h1>

<p><b>Binary Search</b> is an efficient searching algorithm used to find the position of a target element in a <b>sorted array or list</b>. It works by repeatedly dividing the search interval in half.</p>

<h2>Prerequisite</h2>

<p>The data structure must be <b>sorted</b>. Binary search does not work on unsorted data.</p>

<h2>Basic Idea</h2>

<p>Instead of checking every element one by one, binary search compares the target value with the middle element of the array:</p>

<ul>

<li>If the target equals the middle element, the search ends.</li>

<li>If the target is smaller, search continues in the left half.</li>

<li>If the target is larger, search continues in the right half.</li>

</ul>

<h2>Algorithm Steps</h2>

<ol>

<li>Set <b>low</b> to the first index and <b>high</b> to the last index.</li>

<li>Find the middle index: <b>mid = (low + high) / 2</b>.</li>

<li>Compare the middle element with the target.</li>

<li>Repeat until the element is found or the range becomes empty.</li>

</ol>

<h2>Time Complexity</h2>

<ul>

<li><b>Best Case:</b> O(1)</li>

<li><b>Average Case:</b> O(log n)</li>

<li><b>Worst Case:</b> O(log n)</li>

</ul>

<h2>Space Complexity</h2>

<ul>

<li><b>Iterative approach:</b> O(1)</li>

<li><b>Recursive approach:</b> O(log n)</li>

</ul>

<h2>Applications</h2>

<ul>

<li>Searching in large databases</li>

<li>Finding elements in sorted arrays</li>

<li>Used as a base for advanced algorithms</li>

<li>Efficient lookup operations</li>

</ul>

<h2>Advantages</h2>

<ul>

<li>Very fast compared to linear search</li>

<li>Reduces number of comparisons significantly</li>

</ul>

<h2>Limitations</h2>

<ul>

<li>Requires sorted data</li>

<li>Not suitable for linked lists without indexing</li>

</ul>

<p>Binary search is a cornerstone algorithm in computer science and is widely used due to its efficiency and simplicity.</p>