Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Key Concepts

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Searching

In this case, the problem we are trying to solve with search is: given an element N - find that element in a sorted array. The only algorithm worth mentioning here is the binary search.

Binary Search

  • Runtime: O(log N)
  • Recommended reading

As we know that the array is sorted, we can use a divide and conquer approach. Here we will repeatedly divide the array by using the middle point as a pivot. If the element we are after is smaller than this pivot, we will look only to the left-hand side of the array, and start this process all over again.

binary search

By doing this we would reduce the runtime to O(log N), rather than doing a linear search - which would take O(N).

Here is the code in Java:

Recursive approach

int binarySearch(int[] array, int n, int low, int high) {
    if (low > high) return -1;

    int middle = (low + high) / 2;
    int pivot = array[middle];

    if (pivot < n) return binarySearch(array, n, middle + 1, high); // need to go right
    else if (pivot > n) return binarySearch(array, n, low, middle - 1); // need to go left
    else return pivot;
}

Iterative approach

int binarySearchIterative(int[] array, int n) {
    int low = 0;
    int high = array.length - 1;
    int mid, pivot;

    while (low <= high) {
        mid = (low + high) / 2;
        pivot = array[mid];

        if (pivot < n) low = mid + 1;
        else if (pivot > n) high = mid - 1;
        else return pivot;
    }

    return -1; // Error
}
Last updated on 4/4/2020
← SortingRecursion →
  • Binary Search
    • Recursive approach
    • Iterative approach
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr