Algorithms

Merge Sort is another efficient sorting algorithm that follows the divide-and-conquer strategy. It divides the input array into two halves, recursively sorts each half, and then merges them back together.

Here’s how Merge Sort works:

1. Divide: Divide the unsorted array into two halves.

2. Conquer: Recursively sort each half.

3. Merge: Merge the two sorted halves into a single sorted array.

4. Base Case: The base case of the recursion is when the sub-array has zero or one element, in which case it is already considered sorted.

5. Quick Sort 2024-06-07

   Quick Sort is a widely-used sorting algorithm known for its efficiency and simplicity. It follows the divide-and-conquer strategy to sort an array or list of elements.

   Here’s how Quick Sort works:

   1. Partitioning: Choose a pivot element from the array. Rearrange the array so that all elements less than the pivot come before it, and all elements greater than the pivot come after it. After this partitioning step, the pivot element is in its final sorted position.

   2. Binary Search 2022-06-27

      Binary Search is a searching algorithm for finding an element’s position, if it exists, in a sorted array.

      Implementation

      def search(nums, k):
      
      	right = len(nums)
      	left = 0
      
      	while left <= right:
      
      		mid = (left + right) // 2
      		
      		if nums[mid] == k:
      			return mid
      		elif nums[mid] > k:
      			right = mid - 1
      		else:
      			left = mid + 1
      
      	return -1
      

      func search(nums []int, key int) int {
      	left := 0;
      	right := len(nums)
      	var mid int
      
      	for left <= right {
      		mid = left + (right - left) / 2
      		
      		if nums[mid] == key {
      			return mid
      		}
      
      		if nums[mid] < key {
      			left = mid + 1
      		} else {
      			right = mid - 1
      		}
      	}
      	return -1
      }
      

      function search(array, key) {
          let left = 0;
          let right = array.length - 1;
      
          while (left <= right) {
              mid = Math.round( (left + right) / 2 );
              
              if (array[mid] === key) {
                  return mid;
              } else if (array[mid] > key) {
                  right = mid - 1;
              } else {
                  left = mid + 1;
              }
          }
      
          return -1;
      }
      

      int binarySearch(vector nums, int x) {
      	int left = 0;
      	int right = nums.size();
      
      	while (left <= right) {
      		int mid = left + (right - left) / 2;
      
      		if (nums[mid] == x)
      			return mid;
      		if (nums[mid] < x)
      			left = mid + 1;
      		else
      			right = mid - 1;
        	}
        	return -1;
      }
      

      public class BinarySearch {
      
          public static int search(int[] array, int target) {
              int left = 0;
              int right = array.length - 1;
      
              while (left <= right) {
                  int mid = (left + right) / 2;
      
                  if (array[mid] == target) {
                      return mid;
                  } else if (array[mid] > target) {
                      right = mid - 1;
                  } else {
                      left = mid + 1;
                  }
              }
              return -1;
          }
      
      }
      

      Complexity

      Time Complexities

   3. Best Way to Check if a Number Contains Another Number 2022-06-19

      Need to find out if a number contains another number? And you want better performance than converting to a string and then looping through that to find the key number? Well you’ve come to the right place!

      Using a combination of the modulo operator and division it’s possible to pull the number apart one digit at a time until it reaches 0.

      Implementation Using a Loop

      def checkNumberIfContainsKey(number, key):
          while number > 0:
              if number % 10 == key:
                   return True
              number = number // 10
          return False
      

      package main
      
      import "fmt"
      
      func checkNumberIfContainsKey(number, key int) bool {
      	for number > 0 {
      		if number%10 == key {
      			return true
      		}
      		number = number / 10
      	}
      	return false
      }
      
      func main() {
      	fmt.Println(checkNumberIfContainsKey(359, 9))
      }
      

      function checkNumberIfContainsKey(number, key){
          while(number > 0){
              if(number%10 == key){
                  return true;
              }
              number = Math.floor(number / 10);        
          }
          return false;
      }
      

      #include "bits/stdc++.h"
      using namespace std;
      
      bool checkNumberIfContainsKey(int number, int key)
      {
      	while (number > 0) 
      	{
      		if (number % 10 == key) 
      		{
      			return true;
      		}
      		number = number / 10;
      	}
      	return false;
      }
      
      int main(int argc, char const *argv[])
      {
      	cout << checkNumberIfContainsKey(359,9) << endl;
      	return 0;
      }
      

      class ContainsKey {
          public static boolean checkNumberIfContainsKey(int num, int key) {
              while (num > 0) {
                  if (num % 10 == key) {
                      return true;
                  }
                  num = num / 10;
              }
              return false;
          }
      }
      

      Recursive Implementation

      def checkNumberIfContainsKey(number, key):
          if number == 0:
              return False
          
          if number % 10 == key:
              return True
          
          return checkNumberIfContainsKey(number // 10, key)
      

      package main
      
      import "fmt"
      
      func checkNumberIfContainsKey(number, key int) bool {
      	if number == 0 {
      		return false
      	}
      	if number%10 == key {
      		return true
      	}
      	return checkNumberIfContainsKey(number / 10, key)
      	
      }
      
      func main() {
      	fmt.Println(checkNumberIfContainsKey(359, 9))
      }
      

      function checkNumberIfContainsKey(number, key){
          if (number === 0) {
          	return false;
          }
          if(number%10 == key) {
          	return true;
          }
          return checkNumberIfContainsKey(Math.floor(number / 10), key);
      }
      

      #include "bits/stdc++.h"
      using namespace std;
      
      bool checkNumberIfContainsKey(int number, int key)
      {
      	while (number > 0) 
      	{
      		if (number % 10 == key) 
      		{
      			return true;
      		}
      		number = number / 10;
      	}
      	return false;
      }
      
      int main(int argc, char const *argv[])
      {
      	cout << checkNumberIfContainsKey(359,9) << endl;
      	return 0;
      }
      

      class ContainsKey {
          public static boolean checkNumberIfContainsKey(int num, int key) {
              if (num == 0) {
                  return false;
              }
      
              if (num % 10 == key) {
                  return true;
              }
      
              return checkNumberIfContainsKey(num / 10, key);
          }
      }
      

   4. Two Sum 2022-06-19

      Given an array of unsorted numbers nums and an integer target, find two integers in the array that sum to the target and return their indices.

      There are three ways that I know of to solve this problem. Below you’ll find a description of each with some brief code examples. I would like to encourage you to try to implement your own solution first before scrolling down.

      Solution 1: Brute Force

      The first way, which is the brute force method, is to use nested loops. It tries every possible combination by looping over and take exponential time.