Scribd
Upload
3 views1 page

Binary Search Algorithm Explained

Uploaded by

sumitpawar4731
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
3 views1 page

Binary Search Algorithm Explained

Uploaded by

sumitpawar4731
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

Algorithm to Search an Element using Binary

Search
Algorithm:
1 Start
2 Initialize low = 0, high = n - 1
3 Repeat steps 4–7 while low ≤ high:
4 Set mid = (low + high) / 2
5 If A[mid] == key, print 'Element found at position mid' and stop
6 If A[mid] > key, set high = mid - 1
7 Else, set low = mid + 1
8 If loop ends, print 'Element not found'
9 Stop
Step Count Method (Derivation of Time Complexity):
Let the number of elements be n. At each step, Binary Search divides the array into two halves,
reducing the search space by half. The size of search space becomes n/(2^k) after k steps. The
search stops when n/(2^k) = 1 ⇒ k = log■n. Hence, the number of steps required is O(log■n).

Time Complexity Analysis:


• Best Case: Key found in first comparison → O(1).
• Average Case: Key found after few divisions → O(log n).
• Worst Case: Key not present or found after all divisions → O(log n).
Space Complexity:
Iterative implementation → O(1). Recursive implementation → O(log n) due to recursion stack.

Final Summary:
• Algorithm divides search space repeatedly by half.
• Step count = log■n.
• Best Case: O(1), Average/Worst Case: O(log n).
• Space Complexity: O(1) iterative / O(log n) recursive.

You might also like