binary Search Algorithm
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays. In 1957, William Wesley Peterson published the first method for interpolation search.
In 1946, John Mauchly made the first mention of binary search as part of the Moore School lecture, a seminal and foundational college course in computing. In 1962, Hermann Bottenbruch exhibited an ALGOL 60 implementation of binary search that put the comparison for equality at the end, increase the average number of iterations by one, but reduce to one the number of comparisons per iteration.
/* Binary Search-Search a sorted array by repeatedly dividing the search interval
* in half. Begin with an interval covering the whole array. If the value of the
* search key is less than the item in the middle of the interval, narrow the interval
* to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the
* value is found or the interval is empty.
*/
function binarySearch (arr, i) {
var mid = Math.floor(arr.length / 2)
if (arr[mid] === i) {
console.log('match', arr[mid], i)
return arr[mid]
} else if (arr[mid] < i && arr.length > 1) {
binarySearch(arr.splice(mid, Number.MAX_VALUE), i)
} else if (arr[mid] > i && arr.length > 1) {
binarySearch(arr.splice(0, mid), i)
} else {
console.log('not found', i)
return -1
}
}
var ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
binarySearch(ar, 3)
binarySearch(ar, 7)
binarySearch(ar, 13)
