Discover the power of binary search in JavaScript, and don’t miss out on this valuable tool.
In this article, you’ll learn how to find data in sorted arrays faster and more efficiently.
We will discuss examples for implementing both iterative and recursive approaches.
Now, we will continue our deep exploration of binary search in JS. Keep on reading!
What is a binary search?
A binary search is a search algorithm that finds the position of a target value within a sorted array in JavaScript.
It is also called divide-and-conquer algorithm, because it searches faster and more efficiently over a standard linear search.
Binary search works by repeatedly dividing the search interval in half, starting with the middle element of the array.
Here’s an example of how binary search works in JavaScript:
function binarySearch(arr, target) {
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 (array[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
let arr = [10, 30, 40, 50, 80, 90, 100, 170, 100, 120, 230];
let target = 90;
let result = binarySearch(arr, target);
if (result !== -1) {
console.log(`Target found at index: ${result}`);
} else {
console.log("Target not found in array");
}In this example, we have a sorted array of numbers and a target value that we want to find.
The binarySearch function takes the array and the target value as arguments and returns the index of the target value in the array if it is found, or -1 if it is not found.
The function uses a while loop to repeatedly check the middle element of the search range until the target value is found or the search range is exhausted.
If the middle element is equal to the target value, its index is returned. If the middle element is less than the target value, the search continues in the right half of the array.
If the middle element is greater than the target value, the search continues in the left half of the array.
In this example, when we run the code with array and target as defined above, we get the output Target found at index: 5,
Output:
Target found at index: 5
Indicating that the target value 90 was found at index 5 in the array.
When you use this method, the algorithm quickly narrows down the search area by half with each try.
This makes it a speedy and efficient way to find a specific value you’re looking for in a list of items that are in order.
However, remember that binary search can only be used when the items are arranged in a sorted manner.
How to use binary search in JavaScript?
Binary Search is a searching technique that works on the Divide and Conquer approach. It is used to search for any element in a sorted array.
It has a time complexity of O(logN), while linear search has a time complexity of O(N). It simply means that binary search can find an element in a sorted array much more quickly than linear search.
Here’s an example of how you can implement Binary Search in JavaScript using the recursive approach:
let recursiveFunction = function (arr, a, start, end) {
if (start > end) return false;
let mid=Math.floor((start + end)/2);
if (arr[mid]===a) return true;
if(arr[mid] > a)
return recursiveFunction(arr, a, start, mid-1);
else
return recursiveFunction(arr, a, mid+1, end);
}
let arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
let a = 60 ;
if (recursiveFunction(arr, a, 0, arr.length-1))
console.log("Target found!");
else console.log("Target not found!");
Our example code searches for the element a in the sorted array arr using the recursiveFunction that you provided.
The function takes four arguments: the array to be searched, the element to be searched for, the starting index of the search range, and the ending index of the search range.
We are searching for the element 60 in the entire array arr, so we pass 0 as the starting index and arr.length-1 as the ending index.
Output:
Target found!You can also implement Binary Search using an iterative approach:
let iterativeFunction = function (arr, a) {
let start=0, end=arr.length-1;
while (start<=end){
let mid=Math.floor((start + end)/2);
if (arr[mid]===a) return true;
else if (arr[mid] < a)
start = mid + 1;
else
end = mid - 1;
}
return false;
}
let arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
let a = 60 ;
if (iterativeFunction(arr, a))
console.log("Target found!");
else console.log("Target not found!");
Output:
Target found!Conclusion
In conclusion, this article highlights the significance of binary search in JavaScript as an invaluable search algorithm tool for efficiently locating data within sorted arrays.
It introduces the concept of binary search as a divide-and-conquer algorithm, offering faster and more effective searching compared to linear search.
The article provides clear explanations and examples of both iterative and recursive implementations of binary search in JavaScript.
We are hoping that this article provides you with enough information that help you understand the binary search in JavaSript.
If you want to dive into more JavaScript topics, check out the following articles:
Thank you for reading itsourcecoders 😊.
