Binary Search

function binarySearch(arr, seekNum) {
	let startIndex = 0;
	let endIndex = arr.length - 1;
	while (startIndex <= endIndex) {
		const middle = startIndex + Math.floor((endIndex - startIndex) / 2);
		if (seekNum === arr[middle]) {
			return middle;
		}

		if (arr[middle] < seekNum) {
			startIndex = middle + 1;	
		} else {
			endIndex = middle - 1;
		}
	}
	
	return -1
}

How it works

1. split array in half
2. determine if the thing you are looking for is in the left half or right half
3. make the winning half the new base array that you are searching for
4. repeat 1-3 until base array can not be split any further
5. if item remaining is the search key, then give it’s position. If it isn’t, then the item doesn’t exist in the array

info

• keep splitting the array in half until you are left with the result you were looking for
• array must be sorted for binary search to work
• recursive in nature, but is more efficient as a loop
• when duplicates exist, the index of the matching item will not consistently be the first/last/etc duplicate item. Just comes down to where the closest slice hits
  • there are variations of binary search that find the rightmost/leftmost duplicate element
• binary search can also be adapted to approximation searches