BinarySearch Recursive Function


#1

Hello, to everyone…

Currently, I’m working on the BinarySearch recursion method, which would search for a given value in the array and return true/false boolean value based on an outcome weather a given value is found within the array…

The following recursion method accomplishes the task, but it destroys fully or partially the array with the pop() method, which is not allowed according to my instructor Jason Franz.


	function rBinarySearch (arr, num){		
		
		if (isNaN(num) || (num === String(num)) || (num == undefined)){
			return "Invalid Number Input";			
		}		
		if (arr[arr.length - 1] == num){			
			return true;
		}
		if (arr.length == 0) {			
			return false;
		}
		else{
			arr.pop();			
		}
		return rBinarySearch(arr, num);		
	}

	console.log(rBinarySearch([2,-4,5,0,1,-3,15],16));

What else can be done without altering either arr or num passing arguments in the rBinarySearch(arr,num)? It is petty easy to solve this problem, if we pass an additional parameter into a function, which would allows us to run along the array’s container. For example, adding additional a parameter to rBinarySearch(arr, num, index+1) would be a petty straightforward solution. But, how this can be done without adding or altering any passing function arguments?


#2

I guess I did not read very well the description of this assignment in the studying material… the array supposed to be tested for a binary search is presumed to be already SORTED. That, definitely, simplifies a solution to this problem. Anyway, can I use the slice() method to solve it?


	function rBinarySearch (arr, num){		
		
		if (isNaN(num) || (num === String(num)) || (num == undefined)){
			return "Invalid Number Input";			
		}		
		if (arr.length === 0 || arr[arr.length - 1] < num){
    		return false;
		}
		var midpoint = Math.floor(arr.length/2);		
		if (num === arr[midpoint]){
			return true;
		}
		if (num > arr[midpoint]){			
			return rBinarySearch(arr.slice(midpoint, arr.length),num);
		}
		if (num < arr[midpoint]){
			return rBinarySearch(arr.slice(0, midpoint),num);
		}
	}

	console.log(rBinarySearch([4,5,6,8,12,13],13));	

#3

You typically want to avoid using slice. A recommended approach might be to track positions and move those positions according to a comparison.


#4

I’m glad you re-calibrated, because your previous implementation didn’t go well with the whole binary search concept. Take this definition on Wikipedia:

Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Although slice() does not alter the original array, you could find a way as not to use slice() in your implementation. I played with some pointers (variables to store references) to a start, middle and end index. With each recursive call, I would redefine those pointers, based on the condition check I was making in my code, in order to find if I hit the value or not.
You would need to pass those pointers as arguments. I believe is close to what Jason is recommending.

I would, also, advice to use simpler syntax for checks like your first condition:

if (isNaN(num) || (num === String(num)) || (num == undefined)){
  return "Invalid Number Input";			
}

You are basically trying to say “If the input provided for the value to be checked is not a number, your input is invalid”. One simpler way, that does not need any logical operators, would be:

if ( typeof num !== 'number' ) { return 'Invalid...'; }

Good luck! And sorry if any of my remarks are out of place (I’m a newbie, so I don’t really know how to behave).


#5

No worries, Cristian. I’m a newbie in coding and any feedback is useful. There is an endless amount of good stuff in computer programming to learn ahead of me. I have a solid math background, but coding is an unexplored world for me. I wish I would have more time for practice and learning, but I’m one of those who is doomed to change a carrier if I want to tune myself to rapidly developing high tech world. So, any feedback like yours is benefical and welcomed. I’m glad that someone, at least, has responded to one of my topics here showing some evident interest.