Algo Problem: Recursive Binary Search in Javascript.

Valeria — Wed, 11 Nov 2020 23:55:38 +0000

Binary Search is an algorithm that is used to search an element in a sorted array. Yes, the array needs to be sorted in order for the Binary Search algorithm to work.

How does it work?

Let's think of a real-world example, a phone book. Let's say you wanted to call your friend, Val. You know your phone book is sorted in alphabetical order, so you start searching for the letter 'v'. Most people would take the following steps:

1) you open the phone book somewhere in the middle.
2) you land in a specific section, such as the letter 'n'.
3) you know that the letter 'v' comes after the letter 'n', therefore any pages before 'n' will be ignored. You will then go to the middle section between letters 'n' and 'v'.
4) you end up in the 't' section.
5) you know that the letter 't' comes before 'v', so any pages before the letter 't' will be disregarded. You will then flip to the middle section between letters 't' and 'v'.

And so on..Until you find the correct section.
Ultimately, you are using a binary search algorithm to navigate through the phone book. You find the mid point by breaking the list in half, compare your search target to the mid point, disregard one of the halves depending on where the target is most likely to be found, then continue the search in the other half by repeating the process. We apply the same logic when searching for an element in a sorted array.

Let's take a look at the following challenge:

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Our goal is to write an algorithm which will search the given array to find the target. We can traverse through the array in O(n) time where n is the length of the array. However, our goal here is to get the time complexity less than O(n) and that is O(log(n)) time. We can achieve this by solving the problem recursively.

How does this algorithm work?

1) Let's define our binary search function binarySearch that takes in an array and a target. In our case, nums = [-1,0,3,5,9,12] and target = 9.

2) Just like in our phone book example, we first need to break this array in two halves. We can do this by finding the middle index.

3) To find the middle index we will first set our left and right pointers (I'll call them lo and hi). This will also help us track the left and right bounds of the array. Let's add lo and hi as arguments and set lo to 0 and hi to nums.length - 1).

4) Before we continue, we should set our base case. Our function will return -1 when our left pointer is greater than the right pointer. In other words, we are done once the left pointer surpasses the right one.

5) We then calculate the middle index using Math.floor((lo + hi)) / 2 ). We use Math.floor to round the number down. Let's call it middle. In our case, our middle index will be equal to 2.

6) Once the middle index is found, we can now start comparing our target to nums[middle].

7) Let's do the first comparison. Our target (9) is greater than nums[middle] which is 3. It means that we can disregard all the numbers before our middle index because we know that those numbers are going to be smaller. We can do this by moving our lo pointer to the index right after our middle index. We return another call to our binarySearch function where we now pass in a different left pointer (middle + 1).

8) We then repeat the process. Once the target is found, our function will return the middle index.

Algo Problem: Two Sum with JavaScript and Ruby

Valeria — Mon, 21 Sep 2020 16:40:59 +0000

I'm a CodeNewbie and a recent coding bootcamp graduate who's embarked on an algorithm journey in order to prepare for future job interviews. As I conquer algo challenges, I plan to use Dev and Medium as my digital rubber ducks. Here's a classic "Two Sum" problem that is commonly seen in job interviews:

Coding Challenge:

Write a function that takes in a non-empty array of integers and an integer representing a target sum. The function should return the two numbers that sum up to the target sum. If there are no two numbers that sum up to the target sum, the function should return an empty array. You my assume that each input would have at most one pair, and you may not use the same element twice. Numbers can be returned in any order.

Sample Input
array = [3, 5, -4, 8, 11, 1, -1, 6]
targetSum = 10
Sample Output
[-1, 11]

Let's first break down the problem. Our function twoNumSum will take in an array of integers ([3, 5, -4, 8, 11, 1, -1, 6]) and a target sum (10). Our goal is to find two numbers inside our array that add up to the target sum. If we look at our array, numbers -1 and 11 are the only two numbers that add up to 10. The function should then return these two numbers.

There are different ways in which you can solve this problem. We can, of course, solve it by using nested loops (brute force approach) where we iterate over the array twice to find the sum. In other words, we would iterate the array at each number in order to check if adding the number to any other number in the array adds up to the sum. The two for loops approach is an easy solution; however, it isn't an optimal one. Traversing through two for loops will result in a running time of O(n²) , since for each number(array[i]), we have to iterate through the rest of the numbers in the array which runs in O(n) time. It will have a constant space complexity O(1) because we are not creating any temporary storage to store the data. There is a more efficient approach to solving this problem, and that is by using a hash table.

Our hashing approach will result in a faster, more efficient algorithm. We start by creating an empty hash. We will then iterate over the array. As we traverse the array, we have to check if the difference between the current number (array[i]) and the targetSum (in this case it is 10) is found in our hash table. In order to do that, we will create a new variable and call it possibleMatch which would be equal to targetSum-array[i]. If it is found in our hash, then we will return the possibleMatch and our current number (array[i]). In the case where our possibleMatch number isn't found in the hash table, we will then store the number in our hash. This will run in linear O(n) time complexity, since we only need to loop through the array once. Look up in the hash table runs in constant time O(1). However, since we're creating a temporary storage (hash = {}), the space complexity will increase to O(n).

To solve this problem in Ruby, we follow the same logic.

Hashing technique is considered a 'good' solution, but it is not the best one. There are other, more efficient ways to solve this problem. Perhaps I'll leave it for another post.

Source:
AlgoExpert.io, Leet Code

DEV Community: Valeria

Algo Problem: Recursive Binary Search in Javascript.

Algo Problem: Two Sum with JavaScript and Ruby