KEMBAR78
Updated Binary Search | PDF
Scribd
Upload
13 views9 pages

Updated Binary Search

Binary search is an efficient algorithm for searching sorted arrays, utilizing a divide-and-conquer approach to halve the search space. It has a time complexity of O(log n) in the worst case and is widely applied in various fields such as databases and AI. While faster than linear search, it requires sorted data and can have increased space complexity in recursive implementations.

Uploaded by

meakankshasharma098
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views9 pages

Updated Binary Search

Binary search is an efficient algorithm for searching sorted arrays, utilizing a divide-and-conquer approach to halve the search space. It has a time complexity of O(log n) in the worst case and is widely applied in various fields such as databases and AI. While faster than linear search, it requires sorted data and can have increased space complexity in recursive implementations.

Uploaded by

meakankshasharma098
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 9

Binary Search

Prepared by Akanksha Sharma and


Akanksha Bhadoriya
Introduction to Binary Search
• - Binary search is an efficient searching
algorithm for sorted arrays.
• - It follows a divide-and-conquer approach to
reduce search space by half.
• - Used in applications like searching in
databases, libraries, and AI.
Binary Search Algorithm
• 1. Initialize low = 0 and high = n-1.
• 2. Repeat while low ≤ high:
• - Compute mid = (low + high) / 2.
• - If arr[mid] == target, return mid.
• - If arr[mid] < target, set low = mid + 1.
• - Else, set high = mid - 1.
• 3. If not found, return -1.
Visual Example: Binary Search
• Example:
• - Sorted Array: [2, 4, 6, 8, 10, 12, 14]
• - Target: 10
• - Step 1: Check middle (8) → Search right half
• - Step 2: Check middle (12) → Search left half
• - Step 3: Found 10 at correct position.
Additional Example: Binary Search
• Example 2:
• - Sorted Array: [1, 3, 5, 7, 9, 11, 13]
• - Target: 7
• - Step 1: Check middle (7) → Found at correct
position on the first attempt.
Time Complexity Analysis
• - Best Case: O(1) → When the middle element
is the target.
• - Worst Case: O(log n) → Recursively divides
search space by half.
• - Space Complexity: O(1) for iterative, O(log n)
for recursive (due to stack calls).
Advantages & Disadvantages
• Advantages:
• - Faster than linear search (O(n)).
• - Efficient for large datasets.

• Disadvantages:
• - Only works on sorted arrays.
• - Recursion increases space complexity in
recursive approach.
Applications of Binary Search
• - Searching in databases and filesystems.
• - Algorithms like search in a rotated sorted
array.
• - Used in AI, game development, and
computational geometry.
• - Applied in binary search trees (BSTs).
Conclusion
• - Binary search is a powerful and efficient
searching technique.
• - It significantly reduces time complexity
compared to linear search.
• - Widely used in computer science and real-
world applications.

You might also like