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.