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.