Swift : Binary Search with Functional Approach

Just use “.contains()”

Now I know Swift array has the contains method but this is just for fun. Let’s go through the steps we will need. First, we will be checking if have an object Arrays so we will need to extend the Array type. Second, we just want to know if the array contains an object so that is a yes or no answer so we will have a function that returns a Bool. Lastly, this is a Functional Approach so we will use only ‘let’ and recursion (no loops allowed). Let’s get into it.

Step 1

If you don’t know, which I think everyone does by now, but Swift is a Protocol Oriented Programming Language so let’s use some here. We will need Comparable & Equatable.

Here we are extending Array but only when the elements of the array are both Comparable and Equatable. This just means we can compare if one object is larger than the other and we can see if two elements equal each other. Make sure not to use.

Part 2

Let’s just look at the function signature, we want a simple use case at the use site and it needs to return a Bool.

For the function we will first make sure the array is in order. Then, get the middle object of the array. After that, we will have to compare to see if the object at the middle is the object we are looking. Next step, will be to see if the object we are looking for is smaller or larger than the object at the middle. Lastly, we will have to keep using the function with the half of the array that we think the object will be in. Also, there will need to be a check against a case where there is only two elements in the array. If that is the case we will need to check weather the array only has two elements to make sure we don’t get lost in recursion. That should look like this.

One part that is kind of bad-looking is the last line.

You have to put the array into Array() because you have an ArraySlice at that point not an Array.

Here is a Non-Functional Approach.

Sorry if the language was bad, I am working on only using Fry’s words like, Randall Munroe. Last, if you are in HR or your company is hiring Swift developers feel free to reach out to me.