Binary Search is a powerful and efficient algorithm used to find a specific element in a sorted array. Unlike Linear Search, which checks every element one by one, Binary Search divides the array in half at each step, drastically reducing the number of comparisons. This makes it an essential algorithm for beginners who want to understand how to work efficiently with sorted data in TypeScript.
with hands-on learning.
get the skills and confidence to land your next move.
The importance of Binary Search lies in its speed and precision. It is widely used in applications such as searching through databases, looking up words in a dictionary app, or finding values in large datasets. Learning Binary Search also introduces beginners to concepts like recursion, iteration, and array indexing, which are fundamental in programming. By mastering this algorithm, you can quickly locate elements in large datasets with minimal effort.
Program 1: Binary Search Using a While Loop
This program demonstrates the classic iterative approach to Binary Search. It repeatedly narrows down the search space until the target element is found.
function binarySearchIterative(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
let sortedArray: number[] = [1, 3, 5, 7, 9, 11];
let targetValue: number = 7;
console.log("Element found at index:", binarySearchIterative(sortedArray, targetValue));In this program, the search range is divided in half at each step. Beginners can visualize it as repeatedly narrowing down the possibilities until only the target remains. Iterative Binary Search is efficient and easy to implement.
Program 2: Binary Search Using Recursion
Recursion provides a natural way to implement Binary Search by dividing the array in smaller and smaller sections until the element is found.
function binarySearchRecursive(arr: number[], target: number, left: number = 0, right: number = arr.length - 1): number {
if (left > right) return -1;
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
else return binarySearchRecursive(arr, target, left, mid - 1);
}
let numbers: number[] = [2, 4, 6, 8, 10, 12];
let searchValue: number = 10;
console.log("Element found at index:", binarySearchRecursive(numbers, searchValue));This recursive approach is elegant and easy to read. Beginners can understand how the problem breaks into smaller subproblems, which is a key concept in many algorithms.
Program 3: Binary Search for Negative Numbers
Binary Search works naturally with negative numbers as long as the array is sorted.
function binarySearchIterative(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
let negativeArray: number[] = [-20, -10, -5, 0, 5, 10];
let targetNegative: number = -5;
console.log("Element found at index:", binarySearchIterative(negativeArray, targetNegative));Beginners can see that no additional logic is needed for negative values, making Binary Search versatile for all numeric data types.
Program 4: Binary Search for Floating Point Numbers
Binary Search can also handle decimals efficiently in a sorted array.
function binarySearchIterative(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
let floatArray: number[] = [0.5, 1.2, 2.4, 3.6, 4.8];
let targetFloat: number = 3.6;
console.log("Element found at index:", binarySearchIterative(floatArray, targetFloat));This shows beginners that Binary Search is not limited to integers. As long as the array is sorted and comparisons are valid, it works for floating point numbers as well.
Program 5: Binary Search on a Large Array
Binary Search is highly efficient for large datasets. This program demonstrates searching a larger sorted array.
function binarySearchIterative(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
let largeArray: number[] = Array.from({length: 1000}, (_, i) => i * 2); // 0, 2, 4, ..., 1998
let targetLarge: number = 1500;
console.log("Element found at index:", binarySearchIterative(largeArray, targetLarge));Even with a thousand elements, Binary Search quickly locates the target. Beginners can appreciate how dividing the search space improves efficiency compared to checking each element sequentially.
Program 6: Binary Search Returning First Occurrence
When there are duplicate elements, Binary Search can be modified to return the first occurrence of the target.
function binarySearchFirst(arr: number[], target: number): number {
let left = 0, right = arr.length - 1;
let result = -1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
result = mid;
right = mid - 1; // Continue search on left side
} else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
}
let duplicateArray: number[] = [1, 2, 4, 4, 4, 5, 6];
let targetDuplicate: number = 4;
console.log("First occurrence found at index:", binarySearchFirst(duplicateArray, targetDuplicate));This program teaches beginners how to handle duplicates efficiently while using Binary Search.
Program 7: Binary Search for Strings
Binary Search also works on sorted arrays of strings, using alphabetical order for comparisons.
let names: string[] = ["Albus", "Fred", "George", "Harry", "Hermione"];
let searchName: string = "George";
function binarySearchString(arr: string[], target: string): number {
let left = 0, right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
console.log("Element found at index:", binarySearchString(names, searchName));This example shows that Binary Search is useful beyond numbers and can be applied to any sortable dataset.
Program 8: Binary Search Using Recursion on Large Arrays
Binary Search scales well with recursion, even for large datasets, as long as the array is sorted.
function binarySearchRecursive(arr: number[], target: number, left: number = 0, right: number = arr.length - 1): number {
if (left > right) return -1;
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
else return binarySearchRecursive(arr, target, left, mid - 1);
}
let bigArray: number[] = Array.from({length: 500}, (_, i) => i * 3);
let targetBig: number = 300;
console.log("Element found at index:", binarySearchRecursive(bigArray, targetBig));Beginners can see how recursion maintains efficiency while keeping the code elegant and readable.
Frequently Asked Questions (FAQ)
Binary Search is a fundamental algorithm, and beginners often have common questions:
Q1. Can Binary Search be used on unsorted arrays?
No, the array must be sorted for Binary Search to work correctly.
Q2. Is Binary Search faster than Linear Search?
Yes, Binary Search has a time complexity of O(log n), much faster than Linear Search’s O(n) for large arrays.
Q3. Can Binary Search handle negative and floating point numbers?
Yes, as long as the array is sorted and comparisons are valid.
Q4. Can Binary Search be implemented recursively and iteratively?
Yes, both approaches work efficiently, and recursion often provides a cleaner code structure.
Q5. Is Binary Search suitable for large datasets?
Absolutely, it is ideal for large arrays, databases, or any sorted collection where efficiency matters.
Conclusion
Binary Search is an essential algorithm for efficiently searching sorted arrays. In this article, we explored several TypeScript programs demonstrating Binary Search using loops, recursion, duplicates, negative numbers, floating points, strings, and large arrays. Each example illustrated how dividing the search space reduces comparisons and speeds up searches.
By practicing these programs, beginners can understand the power of Binary Search and apply it to a wide range of problems. Mastering this algorithm provides a strong foundation for learning more advanced data structures and algorithms, making your coding skills faster and more efficient.
