Scribd
Upload
5 views3 pages

Recursive Binary Search Algorithm

The document outlines a recursive binary search algorithm that efficiently finds a target value in a sorted array. It includes a detailed explanation of the algorithm's steps, along with two test cases demonstrating its functionality—one where the target is found and another where it is not. The call stack summary provides insight into the recursive calls made during the search process.

Uploaded by

singhritik2728
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
5 views3 pages

Recursive Binary Search Algorithm

The document outlines a recursive binary search algorithm that efficiently finds a target value in a sorted array. It includes a detailed explanation of the algorithm's steps, along with two test cases demonstrating its functionality—one where the target is found and another where it is not. The call stack summary provides insight into the recursive calls made during the search process.

Uploaded by

singhritik2728
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

Binary Search with Recursion

1 Algorithm
1 def binary_search ( arr , target , left =0 , right = None ) :
2 # Step 1: Initialize right boundary on first call
3 if right is None :
4 right = len ( arr ) - 1
5

6 # Step 2: Base case - element not found


7 if left > right :
8 return -1
9

10 # Step 3: Find middle element


11 mid = ( left + right ) // 2
12

13 # Step 4: Check if middle element is the target


14 if arr [ mid ] == target :
15 return mid
16

17 # Step 5: If target is smaller , search left half


18 if arr [ mid ] > target :
19 return binary_search ( arr , target , left , mid - 1)
20

21 # Step 6: If target is larger , search right half


22 return binary_search ( arr , target , mid + 1 , right )

2 Test Case 1: Finding 7 in [1,3,5,7,9,11,13,15]


Initial Function Call

1 print ( binary_search ( sorted_arr , 7) )


2 # binary_search ([1 ,3 ,5 ,7 ,9 ,11 ,13 ,15] , 7 , 0 , None )

Recursive Call 1 (Initial Call)


Input Parameters:

arr = [1, 3, 5, 7, 9, 11, 13, 15]


target = 7
left = 0
right = None
Execution:

• Step 1: right becomes 7


• Step 2: 0 > 7? NO

• Step 3: mid = 3
• Step 4: arr[3] = 7 → FOUND

1
1 3 5 7 9 11 13 15

Result: Element found at index 3

3 Test Case 2: Finding 4 (NOT FOUND case)


Initial Function Call

1 print ( binary_search ( sorted_arr , 4) )

Recursive Call 1
Execution Steps:

• right = 7
• mid = 3 → arr[3] = 7
• 7 > 4 → search LEFT half (0 to 2)

1 3 5 7 9 11 13 15

Recursive Call 2
• left = 0, right = 2
• mid = 1 → arr[1] = 3
• 3 < 4 → search RIGHT half (2 to 2)

1 3 5

Recursive Call 3
• left = 2, right = 2
• mid = 2 → arr[2] = 5
• 5 > 4 → search LEFT half (2 to 1)

Recursive Call 4 (Base Case Hit)


• left = 2, right = 1
• left > right → STOP, return -1

Final Result: -1 (element does not exist)

4 Call Stack Summary


Test Case 1
Call 1 -> mid=3 -> FOUND

2
Test Case 2
Call 1 -> mid=3 -> go LEFT
Call 2 -> mid=1 -> go RIGHT
Call 3 -> mid=2 -> go LEFT
Call 4 -> left > right -> NOT FOUND

You might also like