Binary Search - javascript - why does last item in array cause a Maximum call stack exceeded?

Question

Wrote this to try my hands a building a Binary Search. It is by no means the most refactored code there is but wondering why everything works except when X is the last value in the array (i.e. x = 77)?

function binary_search(x, arr) {
    var len = arr.length - 1 //because index starts at 0
    var min = arr[0]
    var max = arr[0]    
    var new_arr = []

if(x < arr[0] || x > arr[len]) 
    //console.log(arr[len])
    console.log (x + " is not within array range.")
else 
    find_x(x, arr)


function find_x(x, arr) {
    var mid = Math.floor(arr.length/2) //takes care of odd numbered elements in array

    if (x === arr[mid]) 
        console.log("Found " + x)

    else if(x < arr[mid]) 
    {
        max = arr[mid]
        new_arr = arr.slice(0, mid)
        find_x(x, new_arr)
    }
    else if(x > arr[mid]) 
    {
        min = arr[mid]
        new_arr = arr.slice(mid, len)
        find_x(x, new_arr)
    }
    else
        console.log(x + " is not in array.")
}
}

var arr = [1,12,43,55,66,77]
binary_search(77, arr)

Insert a console.log('x=',x,'arr=',arr); as the first line of the find_x function and you shall be illuminated. — Matt
– Matt, Commented Jan 24, 2014 at 0:17
Your implementation is messy, try to avoid free variables and implement it in a way so that a find function only used its scoped variables. Check oli.me.uk/2013/06/08/… as an example of a better implementation — zerkms
– zerkms, Commented Jan 24, 2014 at 0:20

zerkms · Accepted Answer · 2014-01-24 00:16:57Z

1

var len = arr.length

without -1, otherwise you cut off the last element

Zero-based index at which to end extraction. slice extracts up to but not including end.

Found with a google chrome debugger - you should try it some day

JSFiddle: http://jsfiddle.net/HC6yL/

References:

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/slice

answered Jan 24, 2014 at 0:16

zerkms

256k73 gold badges447 silver badges551 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Red Alert · Accepted Answer · 2014-01-24 00:15:41Z

0

Problem is probably here:

new_arr = arr.slice(mid, len)

You never set len within the scope of find_x.

answered Jan 24, 2014 at 0:15

Red Alert

3,8262 gold badges20 silver badges24 bronze badges

Collectives™ on Stack Overflow

Binary Search - javascript - why does last item in array cause a Maximum call stack exceeded?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related