Video here.

I went through an entire data structures and algorithms course and felt like the example code in this video was still a bit foreign and worth taking a close look at. The course I took showed how to sort an unsorted array using “divide and conquer” with a recursive function. This video was not how to sort but how to search a given sorted array for the index of a given element.

The “for loop O(n)” approach

const arr = ["a", "b", "c", "d", "e", "f", "g"]
function findMe(arr, target) {
  for(let i; i < arr.length; i++) {
    if (arr[i] === target) {
      return i
    }
  }
}

The better O(log n) approach

Could use an iterative approach with a while loop or a recursive function

const arr = ["a", "b", "c", "d", "e", "f", "g"]
function findMe(target, start, end) {
  if (start > end) {
    return "Not Found"
  }
  const middle = Math.floor((start + end) / 2)
  if (arr[middle] === target) {
    return "Found it at index: " + i
  }
  if (arr[middle] > target) {
    return findMe(target, start, middle-1)
  }
  if (arr[middle] < target) {
    return findMe(target, middle+1, end)
  }
}

Note: The base case

What’s up with the start and end parameters?

And the function doesn’t have the array passed to it? It’s a global variable

So how would you call this function? wrap the target in strings

Here is what I had:

const arr = ["a", "b", "c", "d", "e", "f", "g"]
function findMe(target, start = 0, end = arr.length - 1) {
  if (start > end) {
    console.log("Not Found")
    return
  }
  const middle = Math.floor((start + end) / 2)
  if (arr[middle] === target) {
    console.log(`Found it at index: ${middle}`)
    return
  }
  if (arr[middle] > target) {
    return findMe(target, start, middle - 1)
  }
  if (arr[middle] < target) {
    return findMe(target, middle + 1, end)
  }
  console.log("Could not find what you were looking for.")
}
findMe("e")

What I didn’t grasp at first:

Why allow start and end to be customized? More flexibility to search only part of the array and not the entire array.

We know the array is sorted but if arr[middle] is a string and target is a string so how will the logic know if one string is greater than the other? By definition, because it’s sorted it will know. If it is not sorted it will not work. If I create an unsorted array of names represented by strings, (meaning “Rick” comes before “Andrew”) then searching for Rick I don’t get anything. But if I then sort the array and try again it works. Creating another example with an array of Fib numbers, if the array is not sorted it will not work.

How are duplicates handled? Depends.