! JavaScript Binary Search.md

JavaScript Binary Search

• binarySearch
  • arr: the sorted array
  • target: item to find
• binarySearchFindFirst
  • arr: the sorted array
  • target: item to find
• binarySearchFindFirstBy
  • arr: the sorted array
  • predicate: the search predicate

binarySearch.js

function binarySearch(arr, target) {
    let start = 0;
    let end = arr.length -1;
    
    while (start <= end)
    {
        const mid = Math.floor((start + end)/2);
        const val = arr[mid];
        
        if (val === target) {
            return mid;
        }
        
        if (val < target)
        {
            start = mid + 1;
        }
        else
        {
            end = mid - 1;
        }
    }
    
    return -1;
}

binarySearchFindFirst.js

function binarySearchFindFirst(arr, target) {
    let start = 0;
    let end = arr.length -1;

    let firstIndex = -1; 
    
    while (start <= end)
    {
        const mid = Math.floor((start + end)/2);
        const val = arr[mid];
        
        if (val < target)
        {
            start = mid + 1;
        }
        else if (val > target)
        {
            end = mid - 1;
        }
        else if (val === target)
        {
            firstIndex = mid;
            end = mid - 1;
        }
    }

    return firstIndex;
}

binarySearchFindFirstBy.js

function binarySearchFindFirstBy(arr, predicate) {
    let start = 0;
    let end = arr.length -1;

    let firstIndex = -1; 
    
    while (start <= end)
    {
        const mid = Math.floor((start + end)/2);
        const val = arr[mid];
        
        if (predicate(val, start, end, mid))
        {
            firstIndex = mid;
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }

    return firstIndex;
}

OrderedTraversal.js

class Node {
    constructor(value, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

function OrderedTraversal(node, visit)
{
    const stack = [];

    let curr = node;
    while(curr || stack.length > 0)
    {
        while (curr)
        {
            stack.push(curr);
            curr = curr.left;
        }
        
        curr = stack.pop();
        visit(curr);
        
        curr = curr.right;
    }
}

TreeLoader.js

class Node {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
    
    print(indent)
    {
        indent = indent || 0;
        console.log(`${'  '.repeat(indent)} + ${this.val}`);
        if (this.left)
            this.left.print(indent + 1);
        if (this.right)
            this.right.print(indent + 1);        
    }
}

function parseTree(str)
{
  const parts = str == "" ? [] : str.split(' ');
  
  function buildTree(nodes) {
      const val = nodes.next().value;
      if (val === 'x') return null;
      const left = buildTree(nodes);
      const right = buildTree(nodes);
      return new Node(parseInt(val), left, right);
  }
  
  return buildTree(parts[Symbol.iterator]());
}

parseTree("421 223 79 42 x x 157 133 x x x 327 x 404 356 x x 415 x x 741 626 x x 887 801 795 x x 842 x x 903 x 977 x x").print();