Searching Algorithms
Finding a specific value is easy if you have a flat array. All you have to do is loop through the array and check if each index is equal to the specified value.
function find(array, valueYouWantToFind){ for (let i=0; i<array.length; i++){ if array[i] === valueYouWantToFind {
return i
}
}
return "not found"
}
The ‘find’ function will take in an array and a value, loop through the array and return the index if the value matches the specified value. If the specified value does not exist in the array, the function will return “not found”. This method of searching is also known as a linear search.
However, this solution will not work if you have nested arrays or objects. So how would you go about searching through a nested object? You would need to utilize a searching algorithm!
Breadth-First vs. Depth-First Algorithms
First, what actually is an algorithm? An algorithm is defined as a process or set of rules to be followed in calculations or other problem-solving operations. For example, do you remember doing long division way back when? You were using an algorithm!
There are two main categories of algorithms used to search through nested objects (also known as trees) are Depth-First Search (DFS) and Breadth-First Search (BFS).
Basically, depth-first will go through all of a node’s children before moving on, whilst breadth-first will traverse through all the adjacent nodes before moving down to the next level. Each one is useful for different purposes. For example, depth-first is more advantageous for games or puzzle problems. Breadth-first is more advantageous for searching nodes that are close to the source node.
For this blog, I will be walking through how to write a Breadth-first search using javascript.
Breadth-First Search
Below is one example of a breadth-first search used to traverse through an array.
function find(array, valueToFind) {let current = array
let queue = []while (current || current === 0) {if (current === valueToFind) {
return current
}if (Array.isArray(current)) {
for (let i = 0; i < current.length; i++) {
queue.push(current[i])
}
}
current = queue.shift()
}return null
}
However, this is not exactly easy to understand by just looking at the code, so let’s break it down piece by piece
1. Set a current variable and an empty queue
function find(array, valueToFind) {let current = array
let queue = []...
The find function takes in two arguments, a nested array and the value that you would like to find. The variable current is created and set equal to the entire array object. The variable queue is also initialized as an empty array.
2. Loop through each index of the array
while (current || current === 0) {...}return null
After the variables have been initialized, we want to start looping through our array using a while loop. After every iteration, the loop will check that the current value exists. The loop will continue to run if current is ‘truthy’ or equal to zero (current will return ‘falsey’ if we do not specifically check that it is zero). If the function has ran through all the values in the array without finding a match, it will return null
3. Compare each index to the desired value
//Inside the while loop...if (current === valueToFind) {
return current
}if (Array.isArray(current)) {
for (let i = 0; i < current.length; i++) {
queue.push(current[i])
}
}
current = queue.shift()
Inside the while loop we want to first check if the value stored in current is equal to the value we want to find. If this is true, the function will return this value. Else, we will check if the value currently stored in current is an array. If it is an array, we will push all the values in that array into the back of the queue. Lastly, we will set current equal to the first item in the queue and also remove that item from the queue. We will then begin again with this value.
Remember that if current is an array, this will return false, even if the value we want is in that array. Once we have pushed the values of that array into queue individually, we will be able to check if any of those values are equal to the value we are looking for.
So say we have the following array:
Array = [1, [2, 3], 4]ValueToFind = 4
What order will we check these values?
Well, at first we will check the entire array. At the end of the first iteration, current will be set to 1 and the queue will be [[2,3],4]. Next iteration, one is not equal to 4, so we will check if it’s an array, which it also isn’t. The new current will be [2,3] and the queue will be [4]. For the next iteration, [2,3] is also not 4, but it is an array. We will take 2 and 3 and push them into the back of the queue, so it now looks like [4,2,3]. Current is now set to 4 and it will be removed from the queue. On the next iteration, 4 is equal to 4 so we will return 4 and exit the loop.
Searching algorithms are very useful when looking for a specified value in a nested object. You might not need to write them every day, but they do come up in interviews every now and then, so it’s worth knowing how they work!
