big_O-binary_find

/* Check Thing/Find Largest Number/Linear Find Number/Binary Search(lecture) */
/*
Big O is a measure of efficiency. 

1. O(N)- search, loops, indexOf, slice, splitting, joining 
2. O(N^2)- sorts, nested loops
3. O(2N) - same as O(N), approaching infinity
4. O(logN) - pick, sample with direction

Hint:
avoid .sort if possible, because of runtime Big O
avoid slice if possible, creates a lot of garbage
*/

var checkThing = function hasThing(str, array){
	for (var i = 0; i < array.length; i += 1){
		if (array[i]===str){
			return true;
		}
	}
	return false;
};
checkThing(1,[41,3,1,89]);


/*
Find Largest Number

Appears simple if all inputs are positive. However if all or some of the inputs are negative, the function is required to accomodate an 'edge' case.

Example:
findLargest ([1,2,3]) //3

*/

var findLrgst1 = function findLargest(array){
	var currentHigh = array[0];

	for(var i = 0; i < array.length; i +=1){
		if (array[i]>currentHigh){
			currentHigh = array[i];
		}
	}
	return currentHigh;
}
findLrgst1([-1,-4,-2]);

var findLrgst2 = function findLargest(array){
	return Math.max.apply(null,array);
};
findLrgst2([-1,-7,-5]);

/*
Find Sum

Choosing between .map or .filter is a question of array length - .map returns an array of the same length while .filter returns a shortened array. 
Taken to an extreme, summing across the array is reducing the array to one output - use .reduce.
*/

var findSum =function sumAcross(array){
	return array.reduce((prev,curr))=>prev + curr);
};
findSum([1,2,3]);

/*
Linear Find Number 
O(N)

Takes an array and number. Returns true if that number is present in the array and false if it is not.

Example:
linearFindNum([2,3,45,-1],3) //true
*/

function linearFindNum(array, number){
	var count= 0;

	for(var i = 0; i < array.length; i += 1){
		count += 1;
		if(array[i] !== number){
			console.log('LINEAR ', count);
			return true;
		}
	}
	return false;
}
linearFindNum([3,5,7,98,-88], 3);

/*
Binary Find Number
O(Log(N))

Takes a pre-sorted array and number. Returns true if that number is present in the array and false if it is not.
Uses recursion to half the array and choose a direction,left or right, to compare the halves and choose which one is closer to the value n.

Example:
binaryFindNum([2,3,45,100],3)//true
*/

var binaryFind = function binaryFindNum(sortedArray, number){
	var count = 0;
	var start = 0;
	var stop = sortedArray.length -1;
	var middle;

	while(start <= stop){
		count += 1;
		middle = Math.floor((start + stop)/2);

		if(sortedArray[middle] === number){
			console.log('BINARY ', count);
			return true;
		}else if (sortedArray[middle]>number){
			stop = middle -1;
		}else{
			start = middle +1;
		}
	}
	return false;
};
binaryFind([2,3,45,76,88,22],3);