Binary Search
Binary Search
Binary Search
Done by
S.Manoj kumar
Binary
Search
• Iterative Binary Search Algorithm: The iterative approach uses a loop to reduce the search
space by half with each iteration until the target element is found or the search space is
exhausted.
• Recursive Binary Search Algorithm: The recursive approach uses the same principle as the
iterative one but divides the problem into smaller sub-problems using recursive calls.
Conditions for when to apply Binary Search in a
DataStructure:
Binary Search is an efficient algorithm for finding an element in a sorted data structure. Here are the
conditions for when to apply Binary Search:
Sorted Data: The data structure must be sorted in order for Binary Search to work correctly.
Direct Access: The data structure should allow direct access to any element in constant time, which is
typical of arrays.
Large Data Sets: It is particularly useful for large data sets because it significantly reduces the number of
comparisons needed compared to linear search.
Contiguous Memory: Binary Search is most efficient when the data is stored in contiguous memory, as in
the case of arrays.
Non-complex Structure: The data should not have complex relationships or structures that would impede
the direct access required by Binary Search.
Advantage Disadvantages
• Fast search time: • Requires sorted data:
Binary search has a time complexity of O(log n), maki The data must be sorted beforehand, which can be a disadv
ng it much faster than linear search for large data sets antage if sorting has not already been done
. .
• Uses less memory: • Not efficient for small arrays:
It doesn’t require additional storage space, as it operate For small data sets, the overhead of the algorithm may not
s directly on the sorted array be worth it, and a linear search could be more practical
. .
• Works on sorted data: • Poor performance on linked lists:
It’s specifically designed for sorted arrays, which is co Binary search requires direct access to the middle elements,
mmon in many applications which is not efficient with linked lists
. .
• Easy to understand: • Repeated elements cause inefficiency:
The algorithm is straightforward, making it simple to l If there are many identical elements, binary search can perf
earn and implement orm unnecessary comparisons
. .
• Efficient for large data: • Not suitable for mutable data:
The larger the data set, the more efficient binary search If the data changes frequently, maintaining a sorted order b
Application of
Binary search
• Searching in Sorted Arrays: The primary use of binary search is to find an element in a sorted array efficiently.
• Finding Square Roots: Binary search can determine if a number is a perfect square by searching through a
range of integer.
• Finding the First Occurrence: It can locate the first element in a sorted array that is greater than or equal to a
given value.
• Computing Frequency: Binary search helps in finding the frequency of a target value in a sorted array of
integers.
• Peak Finding: It’s used to find a peak element in an array where elements first increase and then decrease.
• Rotated Array Search: If a sorted array is rotated, binary search can still find a target value within it
THANK YOU