Divide and Conquer - rohit120582sharma/Documentation GitHub Wiki

Introduction

This pattern involves dividing a data set into smaller chunks and then repeating a process with a subset of data. This pattern can tremendously decrease time complexity.


Binary Search

Given a sorted array of integers, write a function called binarySearch, that accepts a value and returns the index where the value passed to the function is located. If the value is not found, return -1.

Time Complexity - Log(N)

function binarySearch(array, val) {
	let min = 0;
	let max = array.length - 1;

	while (min <= max) {
	    let middle = Math.floor((min + max) / 2);
	    let currentElement = array[middle];

	    if(currentElement < val){
	        min = middle + 1;
	    }
	    else if(currentElement > val){
	        max = middle - 1;
	    }
	    else{
	        return middle;
	    }
	}

	return -1;
}
binarySearch([1,2,3,4,5,6], 3) // 2
binarySearch([1,2,7,9,3,4,5,6], 9) // 3
binarySearch([1,2,3,4,5,6], 11) // -1
⚠️ **GitHub.com Fallback** ⚠️