#2 Interview Preparation | How to find the smallest element of an array ?
Code challenge
Given a non-empty array of numbers, write a recursive function min(…) which returns the smallest element of the input array.
- The difficulty of this challenge is ranked as : Intermediate
- The topic of this challenge is categorized as : Algorithm
Expected output
For whom is this article ?
In this article, we look at an algorithm to find the smallest element of an array of numbers. We provide a coding solution implemented in VBA using the functional programming principles. This article is addressed to the following people :
- People preparing for coding interviews
- People interested in algorithms and recursive thinking
Building the solution
Note : Readers willing to solve this challenge by themselves should stop reading here. Below this point, the solution will be discussed and implemented.
When trying to solve a problem recursively, we need to find a smaller problem that can be solved with the same logic. Let’s rewrite statement (1) and (2)
In (4) we rewrote the original statement (1) with a recursive definition of a smaller size. In the recursion terminology, this is the induction step.
When executing a recursive logic, we also need to make sure it stops. To do so, we use the statement (5) which states that, the min of an array of one element is its unique element. In the recursion terminology, this is the base case.
Now that the induction step and base case are defined logically, we can write them in code.
Coding the min(…) function
This section aims to present a recursive implementation of the function min(…). It is using the principles of functional programming. The below code contains all the auxiliary functions and can be run on your machine simply by copying and pasting it in your coding environment. To reproduce the outputs from the section Expected output, run the method main(). The results for (1), (2) and (3) are respectively stored in variables r1, r2 and r3.
The min(…) function uses the below helper functions. Those functions do not have any side effects meaning that they always create their output without modifying any of their inputs.
- head(xs) : returns the first element of the array xs
- tail(xs) : returns a new array containing all the elements of the array xs except its first element
- size(xs) : returns the size of the array xs
- math_minimum(a, b) : returns the mathematically smallest element between a and b