Binary Search

Summary: Compare the middle element of a sorted array with the target value. If they are unequal, discard the half in which the element cannot lie. Perform the search again. Continue searching on the remaining half until successful. If the search ends with the remaining half empty, target is not in the array.

Purpose: Find the position of a target value within a sorted array Input: Sorted Array

Time Complexity: O(log(n))

Implementation:

const sortedArray = [3, 5, 13, 15, 24, 25, 31, 32, 37, 39, 40, 42, 43, 58]
 
// take in a sorted array and a targetvalue
const binarySearch = (sortedArray: number[], e: number) => {
 
// define the target element e
let targetValue = e;
 
// define the start and end indices
let startIndex = 0;
let endIndex = sortedArray.length - 1 //because .length() counts from 1 to n
 
 
while (startIndex <= endIndex) {
	// Step 1: Find the middle index
	let middleIndex = startIndex + Math.floor(endIndex - startIndex / 2);
	// Step 2: See if the middle index of the array has the target
	// if it does return the index, if not move to Step 3
	if (sortedArray[middleIndex] === targetValue) {
		console.log(`Target value found at index: ${middleIndex}`)
		return middleIndex
	}
	// Step 3: Decide which half from the middle to keep
		// if the target value is greater than the value of the middle index,
		// change the start index to be +1 of the middle index and keep the end index as is
	if (targetValue > sortedArray[middleIndex]) {
		startIndex = middleIndex + 1
	} else {
		// if the target value is less than the value of the middle index,
		// change the end index to be -1 of the middle index, keep the start
		endIndex = middleIndex - 1
	}
	
	}
	console.log("targetValue not found in array")
	return
}
 
binarySearch(sortedArray, 40);
binarySearch(sortedArray, 41);