Binary Search
Binary Search
Understanding Binary Search

The Binary Search is a fast search algorithm that works on sorted lists.

It operates by continuously dividing the list in half until the desired item is found.

If the item being searched for is less than the item in the middle of the list, the algorithm repeats the process on the left half of the list.

If the item being searched for is more than the item in the middle, the right half of the list is considered next.

Binary search concludes when the item is found or when the subarray size becomes zero, which means the desired item is not in the list.
How Binary Search Works

Binary Search begins with the middle element of the sorted list.

If the target value is equal to the middle element of the array, the search ends.

If the target value is less than the middle element, the search continues on the lower half of the array.

If the target value is higher than the middle element, the search continues on the upper half.

The process continues, eliminating half of the elements, and comparing the target value to the middle element of the remaining elements  until the target value is either found (and the index returned), or until the entire array has been searched.
Implementing Binary Search

Binary Search can be implemented recursively or iteratively.

In a recursive approach, the Binary Search function calls itself, each time with a smaller part of the input array.

In the iterative approach, a loop encloses the searching algorithm instead of calling a function with smaller parts of the array.

An iterative approach may be slightly more efficient as it avoids the overhead of recursive calls.
Example of Binary Search

Here’s a simple pseudocode representation for binary search:
FUNCTION BinarySearch(Array, TargetValue) Low = 0 High = Length of Array  1 WHILE Low <= High DO Mid = (Low + High) / 2 IF Array[Mid] < TargetValue THEN Low = Mid + 1 ELSE IF Array[Mid] > TargetValue THEN High = Mid  1 ELSE RETURN Mid ENDIF ENDWHILE RETURN "Not Found" END FUNCTION
Evaluating Binary Search

Binary Search is highly efficient, but only when working with sorted data.

It has a time complexity of O(log n), making it extremely efficient, even with large datasets.

However, it is not suitable for lists that are subject to frequent item additions, as these would need to be sorted first to maintain the efficiency of the binary search.

Always consider the nature of your data set and the frequency of search operations to choose the most appropriate search algorithm.
Understanding Time Complexity

Time Complexity of an algorithm quantifies the amount of time taken by an algorithm to run, as a function of the size of the input to the program.

O(log n) time complexity means that the running time of an algorithm grows logarithmically in proportion to the size of the input data set.

Logarithmic time complexity is great because increasing the amount of data has very little effect on the algorithm’s execution time. This makes binary search a preferred method when dealing with large amounts of sorted data.