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

Question

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')
}

Answer 1

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')
}