Written on 10/04/2021
Binary Search is an important algorithm to know if you are writing computer programs. There are many articles out there and I don't want to re write it again. Anyway, I will mention in the reference section.
You can use binary search to find if value exist in the array or not.
Time Complexity: O(log n)
Things to note:
- Needed sorted array
- Array must includes integer
- You can use this to Find the minimum element in a sorted and rotated array.
- Find square root of a large number in O(logn) time
For testing Javascript codes, I use RunJS which is really easy to use.
Iterative method
Code
function binarySearch(arr, number) {
var start = 0; // start index
var end = arr.length - 1; //end index
while (start <= end) {
var mid = Math.floor((start + end) / 2); //middle index
if (arr[mid] == number) return true;
else if (number < arr[mid]) {
end = mid - 1;
} else if(number > arr[mid]) {
start = mid+1;
} else {
return false;
}
}
}
//Driver code
let arr = [1, 3, 4, 6, 12, 35, 40, 45, 57];
let number = 45;
binarySearch(arr, number);
Recursive Method
// Incomplete ...Coming Soon
function binarySearchRecur(arr, number) {
var start = 0; // start index
var end = arr.length - 1; //end index
}
//Driver code
let arr = [1, 3, 4, 6, 12, 35, 40, 45, 57];
let number = 45;
binarySearch(arr, number);
References: