Binary Search

binary-search.markdown

Binary Search

Binary Search implementation in JavaScript. O(log(n))

A Pen by Vlad Bezden on CodePen.

License.

index.html

    <h1 id="qunit-header">QUnit Test Suite</h1>
    <h2 id="qunit-banner"></h2>
    <div id="qunit-testrunner-toolbar"></div>
    <h2 id="qunit-userAgent"></h2>
    <ol id="qunit-tests"></ol>

script.js

'use strict'

/**
* Binary Search implementation example
*
* @param {number[]} data - sorted array of numbers
* @param {number} item - value that has to be found
* @return {number} - index of the found item in an array, otherwise -1
*/
function binarySearch(data, item) {
	let lowIndex = 0
	let highIndex = data.length - 1
	
	while (lowIndex <= highIndex) {
		let mid = Math.trunc((lowIndex + highIndex) / 2)
		let guess = data[mid]
		if (guess === item) {
			return mid
		} else if (guess < item) {
			lowIndex = mid + 1
		} else if (guess > item) {
			highIndex = mid - 1
		}
	}		
	return -1
}

// Teststs
const data = [0, 1, 2, 5, 7, 11, 20, 22, 45, 75, 100]
QUnit.test("binarySearch tests", (assert) => {
	data.forEach((x, i) => {
		assert.equal(binarySearch(data, x), i)
	})
	assert.equal(binarySearch(data, 99), -1)
})

scripts

<script src="https://cdnjs.cloudflare.com/ajax/libs/qunit/2.0.1/qunit.min.js"></script>

style.css

body {
	background-color: #222;
}

styles

<link href="https://cdnjs.cloudflare.com/ajax/libs/qunit/2.0.1/qunit.min.css" rel="stylesheet" />