CODEWITHSUNDEEP
javascriptbinary-search
JorahFriendzone
JorahFriendzone

Reputation: 433

Binary search exiting early?

I'm trying to find the duplicates of two arrays and one of the arrays is significantly larger so I'm iterating through the smaller array while doing a binary search on the larger array for the number. However, my solution isn't running. 

function bSearch(arr, num) {
  let start = 0
  let end = arr1.length - 1
  while (start <= end) {
    let middle = Math.round(start + end / 2)
    if (arr[middle] === num) {
      return arr[middle]
    } else if (arr[middle] < num) {
      start = middle
    } else {
      end = middle
    }
  }
  return false
}

function dup(arr1, arr2) {
  let output = []
  let shorterArray = arr1.length > arr2.length ? arr2 : arr1
  for (let i = 0; i < shorterArray.length; i++) {
    if (bSearch(arr1, shorterArray[i])) {
      output.push(shorterArray[i])
    }
  }
  return output
}

let arr1 = [1, 2, 3, 5, 6, 7], arr2 = [3, 6, 7, 8, 20]
dup(arr1, arr2)

// should return [3, 5, 7]
// currently only returns [3]

Upvotes: 0

Views: 85

Answers (1)

Georgy
Georgy

Reputation: 2462

A number of small issues here.

  1. bSearch(arr1, shorterArray[i]) - in case of arr1 being short you search only it.

  2. In your binary search you use the length of arr1, not arr for intial end variable declarion.

  3. let middle = Math.round(start + end / 2) - .round() rounds different ways, use .floor().

  4. Math.round((start + end) / 2 - start and end addition should be in brackets

  5. Binary logic should increase or decrease middle, otherwise you end up in infinite loop i.e (6 + 6)/2 === 6

Thus:

if (arr[middle] === num) {
    return arr[middle]
} else if (arr[middle] < num) {
    start = middle + 1
} else {
    end = middle - 1
}

JsBin: https://jsbin.com/ciyusodisi/edit?js,console

Upvotes: 1

Related Questions