Introduction
Binary search is a powerful search algorithm that excels in finding elements within sorted arrays. It leverages the "divide and conquer" approach, repeatedly dividing the search space in half until the target element is located or determined to be absent. This post delves into implementing binary search in JavaScript using iterative and recursive techniques, along with exploring its application for element insertion.
Understanding Binary Search
Assumptions: The input array is sorted in ascending order.
Logic:
1. Initialize start and end indices to point to the beginning and end of the array, respectively.
2. While start is less than or equal to end:
- Calculate the middle index using Math.floor((start + end) / 2).
- If the target element is found at arr[middle]:
- Return the middle index as the element's position.
- If the target element is less than arr[middle]:
- Recalculate end to exclude the right half of the search space (since the array is sorted).
- If the target element is greater than arr[middle]:
- Recalculate start to exclude the left half of the search space.
3. If the loop completes without finding the element, return null (or an appropriate indication of element not found).
Implementation: Iterative Approach
function binaryIterative(arr, target) {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
let middle = Math.floor((start + end) / 2);
if (arr[middle] === target) {
return middle;
} else if (target < arr[middle]) {
end = middle - 1;
} else {
start = middle + 1;
}
}
return 'Not found;
}
console.log(binaryIterative([2, 7, 9, 11, 25], 10)); // Output: Not found
Implementation: Recursive Approach
function binaryRecursive(arr, start, end, target) {
if (start > end) {
return 'Element Not Found'; // Or any appropriate indication
}
let middle = Math.floor((start + end) / 2);
if (arr[middle] === target) {
return middle;
} else if (target < arr[middle]) {
return binaryRecursive(arr, start, middle - 1, target);
} else {
return binaryRecursive(arr, middle + 1, end, target);
}
}
function findElement(arr, target) {
let start = 0;
let end = arr.length - 1;
return binaryRecursive(arr, start, end, target);
}
console.log(findElement([2, 7, 9, 11, 25], 9)); // Output: 2
Choosing the Approach
- Iterative: Generally preferred for larger arrays, as it avoids the overhead of function calls associated with recursion.
- Recursive: Can be more concise and easier to understand.
Problem I: Finding or Inserting an Element
The provided searchInsertKfunction demonstrates how to modify the binary search to find the appropriate insertion point for an element in a sorted array:
function searchInsertK(arr, N, K) {
let start = 0;
let end = N - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (K === arr[mid]) {
return mid; // Element found
} else if (K < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
// If not found, return the insertion index (after the last element where K is greater)
return end + 1;
}
Binary search is an essential algorithm for efficient searching in sorted arrays. Understanding its iterative and recursive implementations provides valuable tools.
Top comments (0)