CODEWITHSUNDEEP
javascriptrecursionbinary-search
hughm-01
hughm-01

Reputation: 35

Binary Search, Recursion Method, Returning the wrong output - js

I am trying to do a basic binary search for a value in an array using the recursion method. I used the Iterative method on this same array and got the right output. But this code is returning false (element is not in the array) regardless of whether the input is in the array or not. 

let recursionFunction = function (arr, x, start, end) {
  if (start > end) {
    return false
  }
  let mid = Math.floor((start + end)/2)
  if (arr[mid] == x) {
    return true
  }
  if (arr[mid] > x) {
    return recursionFunction(arr, x, start, mid-1)
  } else {
    return recursionFunction(arr, x, mid+1, end)
  }
}
let x = 91
let arr = [28, 91, 30, 33, 2, 7, 88, 90, 70, 44, 40, 41]
if (recursionFunction(arr, x, 0, arr.length-1)) {
  console.log("element is found in arr")
} else {
  console.log('element is not found in arr')
}

Upvotes: 0

Views: 58

Answers (3)

Prince Hernandez
Prince Hernandez

Reputation: 3721

as stated in the comments, your array should be ordered in order to the binary search to work, think of the steps for your provided array ([28, 91, 30, 33, 2, 7, 88, 90, 70, 44, 40, 41])

in the first step it will take the value in the middle of the array (7) which will be lower than the value that you look (91) then it will reduce your array to ([88, 90, 70, 44, 40, 41]) and then you can notice why your item is not found.

using sort in front of your array fixes the issue :)

5 7 8 70 10 40 11 41 element is not found in arr

let recursionFunction = function (arr, x, start, end) {
  if (start > end) {
    return false
  }
  let mid = Math.floor((start + end)/2)
  console.log(mid, arr[mid])
  if (arr[mid] == x) {
    return true
  }
  if (arr[mid] > x) {
    return recursionFunction(arr, x, start, mid-1)
  } else {
    return recursionFunction(arr, x, mid+1, end)
  }
}
let x = 91
// with sort, it will work.
let arr = [28, 91, 30, 33, 2, 7, 88, 90, 70, 44, 40, 41].sort();
if (recursionFunction(arr, x, 0, arr.length-1)) {
  console.log("element is found in arr")
} else {
  console.log('element is not found in arr')
}

Upvotes: 1

Dan Fletcher
Dan Fletcher

Reputation: 1228

You just have to sort your array before performing the binary search. So on line 16 where you create your example data just add .sort() to the end.

Binary search isn't possible with an unsorted data set.

I assume you're doing this just for the sake of learning but I want to point out that most programming languages will use binary search under the hood if your list is sorted and you perform a find. Which is why it's important to understand it as a concept but it would be incredibly unlikely you'd ever have to implement it yourself.

Upvotes: 1

Dani007
Dani007

Reputation: 151

Your array needs to be sorted for a binary search. It checks to see if 91 is in the middle, no then since 91 is greater than 7, it checks [mid+1, end].

Upvotes: 1

Related Questions