View profile

Day #2: Binary Search & Tail Recursion

Puppy Nomadic
Puppy Nomadic
Binary Search
Today, our study group went over two approaches for implementing binary search – recursive & iterative – and O(log n) time complexity.
We talked about “divide and conquer” algorithms, and why this particular way of finding the target number in an array by finding the midpoint of each sub-array, cut the number of objects to compare with in half with each operation. This is what gives the method logarithmic O(log n) time complexity.
Here is the iterative way of solving Binary Search in Javascript:
let iterativeFunction = function (arr, x) {
    let start=0, end=arr.length-1;
    while (start<=end){
        let mid=Math.floor((start + end)/2);
        if (arr[mid]===x) return true;
        else if (arr[mid] < x)
             start = mid + 1;
        else
             end = mid - 1;
    }
    return false;
}
Here is the recursive way of solving Binary Search in Javascript:
let recursiveFunction = function (arr, x, start, end) {
    // Base Condition
    if (start > end) return false;
    // Find the middle index
    let mid=Math.floor((start + end)/2);
    // Compare mid with given key x
    if (arr[mid]===x) return true;
         
    // If element at mid is greater than x,
    // search in the left half of mid
    if(arr[mid] > x)
        return recursiveFunction(arr, x, start, mid-1);
    else
 
        // If element at mid is smaller than x,
        // search in the right half of mid
        return recursiveFunction(arr, x, mid+1, end);
}
[A deeper explanation is available in the GeekforGeek link below]
Our study group also helped each other troubleshoot some git & dev environment setup issues.
Binary Search In JavaScript - GeeksforGeeks
Divide and conquer algorithms (article) | Khan Academy
Free Books
Mariko shared a useful link of free algorithm books on Github, and recommended reading the illustrated “Grokking Algorithms” (linked below)
Grokking Algorithms - An illustrated guide for programmers and other curious people
Amazing Library of Free Algorithm Books on Github
Three Types of Recursion
On our Slack channel, Tran also brought up tail recursion: what is it? and why it more optimal than other types of recursion?
This article lists three types of recursion:
  1. Tail recursion
  2. Non-tail recursion
  3. Tree recursion
Tail recursion can be automatically optimized by a compiler into a loop.
Indirect/Mutual recursion:
func1 calls func2 which calls func1
Types of Recursion With Examples - The Crazy Programmer
Recursion and tail recursion with JavaScript - DEV Community
Did you enjoy this issue? Yes No
Puppy Nomadic
Puppy Nomadic @puppynomadic

Let's pull each other up by our Bootstrap.js 🪴 👩🏻‍💻 🦮

=== Journey of software craftsmanship ===

{"Formerly": ["nonprofit community organizer", "teacher", "researcher", "government director"],
"Future": ["software engineer", "web3 dev", "developer advocate", "technical program manager"]
}

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.