Lab 3: Binary Search
Target:
geca-labs/lab-daa-03
OR
Continue with your 👇 existing repo
In this lab, we explore binary search, a fundamental search algorithm for sorted arrays. We implement binary search using both recursive and iterative approaches, analyze their time and space complexities, and provide code examples in Python, C++, and JavaScript.
We demonstrate both:
- Recursive implementation (divide and conquer)
- Iterative implementation (using loops)
Mathematical Definition
Given a sorted array and a target value , binary search recursively or iteratively finds an index such that , or reports that is not in the array.
Recursive definition:
Implementation
# Recursive binary search
def binary_search_recursive(arr, low, high, x):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif x < arr[mid]:
return binary_search_recursive(arr, low, mid - 1, x)
else:
return binary_search_recursive(arr, mid + 1, high, x)
# Iterative binary search
def binary_search_iterative(arr, x):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif x < arr[mid]:
high = mid - 1
else:
low = mid + 1
return -1
# Driver
arr = [1, 3, 5, 7, 9, 11]
x = 7
print("Recursive:", binary_search_recursive(arr, 0, len(arr)-1, x))
print("Iterative:", binary_search_iterative(arr, x))C++
#include <iostream>
using namespace std;
// Recursive binary search
int binary_search_recursive(int arr[], int low, int high, int x) {
if (low > high)
return -1;
int mid = (low + high) / 2;
if (arr[mid] == x)
return mid;
else if (x < arr[mid])
return binary_search_recursive(arr, low, mid - 1, x);
else
return binary_search_recursive(arr, mid + 1, high, x);
}
// Iterative binary search
int binary_search_iterative(int arr[], int n, int x) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == x)
return mid;
else if (x < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 7;
cout << "Recursive: " << binary_search_recursive(arr, 0, n-1, x) << endl;
cout << "Iterative: " << binary_search_iterative(arr, n, x) << endl;
return 0;
}JavaScript
// Recursive binary search
function binary_search_recursive(arr, low, high, x) {
if (low > high) return -1;
const mid = Math.floor((low + high) / 2);
if (arr[mid] === x) return mid;
else if (x < arr[mid]) return binary_search_recursive(arr, low, mid - 1, x);
else return binary_search_recursive(arr, mid + 1, high, x);
}
// Iterative binary search
function binary_search_iterative(arr, x) {
let low = 0,
high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === x) return mid;
else if (x < arr[mid]) high = mid - 1;
else low = mid + 1;
}
return -1;
}
// Driver
const arr = [1, 3, 5, 7, 9, 11];
const x = 7;
console.log("Recursive:", binary_search_recursive(arr, 0, arr.length - 1, x));
console.log("Iterative:", binary_search_iterative(arr, x));Expected Output
Recursive: 3
Iterative: 3Both methods return the index
3sincearr[3] = 7.
Time and Space Complexity Analysis
| Method | Time Complexity | Space Complexity |
|---|---|---|
| Recursive | (call stack) | |
| Iterative |
Practice
LeetCode
-
Binary Search - LeetCode #704
A straightforward binary search problem. Implement both iterative and recursive solutions to find a target in a sorted array. -
Search Insert Position - LeetCode #35
Modify binary search to return the index where a target should be inserted if it is not found. Practice handling edge cases. -
Find First and Last Position of Element in Sorted Array - LeetCode #34
Use binary search to determine the starting and ending indices of a target value in a sorted array. Combines multiple binary search adaptations. -
Search in Rotated Sorted Array - LeetCode #33
Adapt binary search for a sorted array that has been rotated. Practice conditional checks and index adjustments. -
Sqrt(x) - LeetCode #69
Apply binary search to find the integer square root of a number. Useful for understanding numeric bounds and floor operations. -
Peak Index in a Mountain Array - LeetCode #852
Use binary search to find the peak element in a bitonic (mountain) array. Enhances understanding of searching in special patterns.
References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
Introduction to Algorithms, 3rd/4th Edition, MIT Press.