6) Binary Search

Okay this is my first shot:

class TreeNode{
  constructor(val, left, right){
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}
 
function createBinaryTree(source, index){
 
  if (index >= source.length || source[index] === null) return null
  
    return new TreeNode(
        source[index],
        createBinaryTree(source, index * 2 + 1),
        createBinaryTree(source, index * 2 + 2),
    )
}
 
var search = function(nums, target) {
  let index = 0
  let tree = createBinaryTree(nums, 0)
  let searchOrderedTree = function(root, target){
    if (root.val === target) return index
    if (root.left.val > target){
      index = index * 2 + 1
      return searchOrderedTree(root.left, target)
    }
    
    if (root.right.val < target) {
      index = index * 2 + 2
      return searchOrderedTree(root.right, target)
    }
 
    return -1
 
  }
 
  return searchOrderedTree(tree, target)
};
 
search([-1,0,3,5,9,12])

I borrowed the binary tree builder from the binary tree inversion that I messed up (because I never needed to build it to begin with) but I think this time it’s useful?

Seems like a lot of code.

Using a binary tree for search is really fun, but I’m not yet sure if it makes any sense and, if anything, stemmed from conflating the terms “binary tree” and “binary search”.

Here is a more traditional, working approach to binary search, where I have commented the gotchas I stumbled over:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target, start=0) {
    // Handle case where there are no, or only one item in array
    if (nums === null || nums.length === 0) return -1
 
    // Handle case where there is only one item in the array
    if (nums.length === 1) {
        return nums[0] === target ? start : -1; // Gotcha - return index start, not index 0!
    }
 
    // Okay looks like there are at least two items in array
 
    let middle = Math.floor(nums.length/2)
    if (nums[middle] === target) return middle + start
 
    // Search the right half of the array
    if (target > nums[middle]){ // Gotcha - compare target with nums[middle], not just with middle
    // I.e. don't get index and target value mixed up
        return search(nums.slice(middle+1), target, start + middle + 1) // gotcha - did not RETURN
        // Another gotcha - remember to add start to middle
        // Nice touch - because we are not cutting off the end, we can pass just one index to slice
 
    // Search the left half of the array
    } else {
        return search(nums.slice(0, middle), target, start)
        // because the beginning of the array is being maintained here, we can pass JUST start, no middle needed
    }
 
};

Gotchas

Not returning the recursive cases This recursive function does not mutate existing variables. Instead, it returns the value from each recursion step. If we forget to return in the recursive cases, the recursion chain breaks, and the function fails to provide a result - unless a base case is hit directly.

Think of it this way: the function must always return something. It returns a value when it finds the target or exhausts all possibilities. This can happen at any recursion level. If we don’t return a base case, we return the recursive function itself to ensure the base case can eventually be returned.

Typo: slice I had a brain fart and typed slice[] instead of slice().

Not adding +1 to an index when passing it in the right half search case By the time we are flowing into the right-half-search-case, we have determined already that the target is

• Not in the left half
• Not at the middle index

Sure, the middle may not be the exact middle of the array if the array is an even number, but that’s irrelevant. What matters is that we checked that index, and the target isn’t there. So when we use slice to pass a subsection of the initial nums array, we have to remember that the first argument slice takes is inclusive. So rather than include the middle index we already checked, we should start our subarray at middle + 1

Not adding start to middle on the right-half-search-case The whole point of passing start is to “remember” the index history. It’s interesting to note that this is only relevant to the right-half-search-case. On the left half search case, the start point stays the same in that recursion. If the start point was 0, it stays 0. If the start point has been moved in some right-half-case-search executed previously, it stays at that index. We don’t have to move the index, because only the endpoint of our starting array is modified. The beginning is in the same place relevant to what that recursion loop started with.

nums/2 instead of nums.length/2 Yes. This is a mistake I made. Results in NaN in case you are curious.

Simplified

Chat GPT also showed me this:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target, start = 0) {
    // Empty array base case
    if (nums.length === 0) return -1;
 
    // Calculate the middle index
    let middle = Math.floor(nums.length / 2);
 
    // Check if the middle element is the target
    if (nums[middle] === target) return middle + start;
 
    // Search the right half of the array
    if (nums[middle] < target) {
        return search(nums.slice(middle + 1), target, start + middle + 1);
    } else {
        // Search the left half of the array
        return search(nums.slice(0, middle), target, start);
    }
};

It has an improved base case that I wouldn’t think would work.

Mansi and Anisha coding session:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchThing = function(nums, target, start, end) { // target=0
    console.log("start", start, "end", end)
 
    let middle = Math.floor((start + end)/2) // 2/2 =1 middle value is 1, index is 1
    let middleNum = nums[middle]
 
    if (middleNum === target) { // 2 == 4
        return middle
    }
 
    if (middle === start || middle === end) {
        return -1
    }
 
    if (middleNum > target){ // 2 < 4 
        return searchThing(nums, target, start, middle) // index //start point, //endpoint
    }
 
    if (middleNum < target) {
        return searchThing(nums, target, middle, end) // nums, 0, 0, 0
    }
 
}
 
var search = function(nums, target) {
    return searchThing(nums, target, 0, nums.length)
}

AHH. This algorithm has given me so much trouble. I’m in a situation where I know the anatomy of it very well - it has 4 parts:

1) Calculating the middle

Usually const mid = Math.floor((left + right) / 2)

2) Unsuccessful Base Case

Determine that the search window has narrowed to an extent that precludes the presence of the target, i.e.

• if (left > right)
• (middle === left || middle === right)
• or the very tempting else condition after our two left and right searches

3) Successful Base Case

Check if the middle equals the target, usually just if (nums[mid] === target

4) Actual Right Left Search

if (nums[mid] < target) search right if (nums[mid] > target search left

Unfortunately, implementing these is easier said than done. All of the indexes, and initial values can be a little finicky to get right. I’m going to go through and try to set it with the following attitude; don’t let anything by. Make sure that every step taken captures all possibilities.

The code I settled on:

var search = function(nums, target, left=0, right=nums.length-1) {
 
    if (left === right) return -1
    
    const mid = Math.floor((right + left)/2)
    if (nums[mid] === target) return mid
    
    if (nums[mid] < target)return search(nums, target, mid + 1, right)
    return search(nums, target, left, mid - 1)
};

The trickiest parts about this to me

I think the trickiest line for me here is the if (left===right) return -1, because at first it didn’t really seem clear how this happens.

I still haven’t really followed it down to the atomic level.

In the case of an odd list, we actually end up finding the target organically between it’s two neighbors in a slice of 3.

But because we are using Math.floor, an even numbered list will actually follow the exact same execution pattern. I’ve only followed this execution pattern going left, but in both of these cases, left and right end up being separated by one index value. So theoretically, using if (left = right -1) would execute slightly sooner, and just as cleanly. Let’s try it.

Nope.

The verdict is, the soonest we can determine target isn’t present seems to be if (left===right). I am having trouble following this all the way to the end, but that seems to be the closest we can get.

Things I learned

• Recursion can definitely be tricky to reason about - it may be worth trying iterate approaches
• The JavaScript slice function can take one or two arguments. If it just takes one, it assumes the end of the returned array is the same. If it takes 2, the second argument determines the one index after the last index returned. In this way, the first index given is inclusive and the second is exclusive, like some annoying bookend
• It is possible to set a default value for a parameter in a function that is calculated as a result of another paremeter, i.e. function binaryearch(nums, target, left = 0, right = nums.length - 1
• Math.floor can be used as a brief and effective method for collapsing sets of two possible integer conditions into one
• ^ Not related to binary search, but this same method is also used in a binary heap priority queue to find the a single parent from either of two potential indexes

Reflections on our failure base case after a few days

Okay so first off I want to say that I found another way to think of the anatomy of this function. It has five parts in this order:

1. failure base case
2. middle declaration and calculation
3. success base case
4. recursive right search commitment
5. recursive left search commitment

And I feel rock solid on all five parts except numero uno, failure base case. I’ve tried to follow the values through the recursion that causes this to either get fired eventually or never get fired, and I’ve really had trouble doing this because it takes a long time to feel that I’ve covered every potential iteration. For example, left search followed by right, right by left, or left by left, or right by right, etc.

However, after thinking about it for a couple of days, I think I almost understand. What does make sense to me is that, if our left and right pointers have collapsed almost into each other - let’s say they are 24 and 25- then we now have a 50% chance of finding out that our middle is our target left.

That is why I am actually unconvinced that left === right is the right condition to check for our base failure case. I am now of the mind - even though leetcode will accept the above condition - that only left > right would be correct. This is because if left === right is true, I think we still need to do one last check that nums[middle] === target, as we have not yet done this check. Once we’ve done that, left and right will have passed each other and we can now rest easy.

Or, I think it would also be acceptable to continue using left === right but to put it after or nums[middle] === target check.

That said, I doubt leetcode is wrong to accept my submission. But that means I am still missing something.

Revisit #1

Okay it’s been a month or so. I’m going to revisit this and see how I do. The code I have recorded above isn’t quite right. The line left===right should be left>right in order for the case nums=[5], target=5 to pass.

I have little idea how the edges of all this work anymore so I’m going to go back through it.

Here’s code with my review notes:

// [1, 2, 3], look for 3, then look for 1
 
var search = function(nums, target, left=0, right=nums.length-1) {
    // we successfully created a window inclusive of 0, 1, 2 as indexes, which matches
    // 1, 2, 3
    if (left > right) return -1 // if left and right are equal,
    // this actually describes an edge case where we are given one list with only one integer
    // So while for all other cases I know of, left === right would be adequate...
    // I dunno think about it. If left and right are equal, we are actually down to a single index to check
    // And that single index might contain our target. No need to stop there.
    const mid = Math.floor((right + left)/2)
    // Because then we get the mid, which might be 0. That's valid. It might also be the same as right or left on its own; also valid.
    if (nums[mid] === target) return mid // if the mid IS what we want, nice! Return it
    if (nums[mid] < target)return search(nums, target, mid + 1, right)
    // If mid is less than target, we should def search on the right side. We've already checked the mid, and know IT'S not going to contain our target, so we can recursively search again with our left as mid + 1, exluding our last mid value, but still including our right as a possible thing to search (might be right! We don't know)
    return search(nums, target, left, mid - 1)
    // Otherwise our target is more than mid. Search the left side. 
};

Okay well, revisited it, got back to about 2 minutes for recall. Let me try one thing.