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.