There are many types of search, including linear, binary and binary tree searches.
This page focuses on the binary search, which in my opinion is the most interesting one.
A binary search requires the list to first be sorted. Once you have a sorted list, the midpoint of the list is found. A check is then run to see if your target item is higher or lower than the midpoint. Any items below/above the midpoint are ignored based on if they are in the direction of the target.
For example, if the midpoint was 5 and the target was 3, anything above 5 inclusive would be ignored, leaving a new shorter list to check.
This then repeats until the midpoint is the target, at which point the search has found its target, or until there are no items left and the list didn't contain the target
Below is an interactive simulation of a binary search.
Target number:
Search speed:
The code for this would look something like this:
function binarySearch(array, target) {
let midpoint = Math.floor((array.length - 1) / 2);
while (array.length > 0) {
if (array[midpoint] === target) {
return midpoint;
} else if (array[midpoint] < target) {
array=array.slice(midpoint + 1);
} else {
array=array.slice(0, midpoint);
}
midpoint=Math.floor((array.length - 1) / 2);
}
return -1;
}