binary-search
Binary search is a powerful algorithm used to efficiently find the position of a target value within a sorted array or list. Its effectiveness lies in its ability to eliminate half of the remaining elements in each step, resulting in a logarithmic time complexity of O(log n), where n is the number of elements in the array.
Let’s break down how binary search works and provide a practical example in JavaScript.
1 – Initial Setup:
low
and high
, to the first and last indices of the array.2 – Middle Element:
mid = Math.floor((low + high) / 2)
.3 – Comparison:
4 – Three Possible Cases:
high
to mid - 1
and search in the left half.low
to mid + 1
and search in the right half.5 – Repeat:
low
exceeds high
.6 – Termination:
low
is greater than high
, the target value is not in the array.Let’s implement a binary search algorithm in JavaScript:
function binarySearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid; // Target found, return the index
} else if (arr[mid] > target) {
high = mid - 1; // Search in the left half
} else {
low = mid + 1; // Search in the right half
}
}
return -1; // Target not found
}
// Example usage:
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const targetValue = 7;
const result = binarySearch(sortedArray, targetValue);
if (result !== -1) {
console.log(`Target ${targetValue} found at index ${result}.`);
} else {
console.log(`Target ${targetValue} not found in the array.`);
}
In this example, we use a binarySearch
function to find the index of a target value in a sorted array. The function returns the index if the target is found and -1 otherwise.
Feel free to use this binary search algorithm in your projects when dealing with sorted data. Its efficiency makes it a valuable tool, especially for large datasets. Happy coding!
One of the common questions among Docker users is whether Docker containers consume disk space.…
Sorting data is a common operation in programming, allowing you to organize information in a…
Splitting a string into an array of substrings is a common operation in C# programming,…
Starting the Docker daemon is the first step towards managing Docker containers and images on…
Serializing an object to JSON (JavaScript Object Notation) format is a common task in C#…
When running Docker containers, you may encounter scenarios where containers need to access resources outside…