-Intro to Searching
-Intro to Linear Search
-Intro to Binary Search
Intro to Searching
Searching is a commonly used functionality for applications. Search engines such as google optimize their results based on a complex algorithm. Youtube has a search algorithm for finding and recommending videos. Searching is a fundamental procedure for applications to be useful. There are many different methods for implementing a search algorithm. Certain situations may make more sense to use a specific search over another.
Intro to Linear Search
JavaScript includes many array methods for search algorithms. Some are indexOf, includes, find, findIndex.
Linear search functions by moving one interval at a time. As well as eliminate one element at a time.
Linear Search Examples
function linearSearch(arr, val){
for(var i = 0; i < arr.length; i++){
if(arr[i] === val) return i;
}
return -1;
}
linearSearch([34,51,1,2,3,45,56,687], 100)
Intro to Binary Search
Binary search is more efficient than linear search because instead of eliminating one element at a time, its eliminates half of the remaining elements at a time.
Binary Search Example
function binarySearch(arr, elem) {
var start = 0;
var end = arr.length - 1;
var middle = Math.floor((start + end) / 2);
while(arr[middle] !== elem && start <= end) {
if(elem < arr[middle]){
end = middle - 1;
} else {
start = middle + 1;
}
middle = Math.floor((start + end) / 2);
}
if(arr[middle] === elem){
return middle;
}
return -1;
}
// Refactored Version
function binarySearch(arr, elem) {
var start = 0;
var end = arr.length - 1;
var middle = Math.floor((start + end) / 2);
while(arr[middle] !== elem && start <= end) {
if(elem < arr[middle]) end = middle - 1;
else start = middle + 1;
middle = Math.floor((start + end) / 2);
}
return arr[middle] === elem ? middle : -1;
}
binarySearch([2,5,6,9,13,15,28,30], 103)
Top comments (0)