Binary Search

Download as pptx, pdf, or txt
Download as pptx, pdf, or txt
You are on page 1of 9

Binary Search

Done by
S.Manoj kumar
Binary
Search

Binary Search is a fundamental algorithm used


for searching within a sorted array. Its primary
advantage lies in its ability to significantly
reduce the search time complexity to O(log N).
how to work in Binary Search
Initialize: Start with two pointers representing the bounds of the array: low (beginning of the array) and high (end of the
array).
Find the Middle: Calculate the middle index mid as low + (high - low) / 2.

Compare: Check if the middle element is equal to the target value.


• If it is, the search is complete.
• If the middle element is greater than the target, narrow the search to the left half by setting high to mid - 1.
• If the middle element is less than the target, narrow the search to the right half by setting low to mid + 1.
Repeat: Continue steps 2 and 3 until the target value is found or the low pointer exceeds the high pointer, indicating the
target is not in the array.
Complexity Analysis of Binary
Search:
Time Complexity:
• Best Case: The best-case scenario occurs when the target value is located at the midpoint of the array during the first comparison. This
results in a complexity of ( O(1) ) because only a single comparison is made.
• Average Case: On average, the algorithm splits the array into halves to find the target value. This means that with each iteration, the
size of the problem is reduced by half, leading to a logarithmic time complexity, which is ( O(\log N) ).
• Worst Case: The worst-case scenario happens when the target value is at one end of the array or not present at all. In such cases, the
algorithm will perform the maximum number of splits possible, which also results in a time complexity of ( O(\log N) ).
• Auxiliary Space:
• Iterative Method: When using the iterative method, the space complexity remains constant, ( O(1) ), because the algorithm uses a fixed
amount of additional space (for variables like low, high, and mid).
• Recursive Method: If the binary search is implemented recursively, the auxiliary space depends on the height of the recursion tree,
which is ( O(\log N) ). This is because each recursive call adds a new layer to the call stack, and the maximum depth of the recursion
tree is proportional to the number of times the array can be halved, which is ( \log N ).
How to Implement Binary
Search?
The Binary Search Algorithm can be implemented in the following two ways

• 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

You might also like