Binary Search

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Breadth First Search (BFS) vs Deep First Search (DFS)

There are two search algorithms exist for binary tree: breadth-first search (BFS) and depth-first search (DFS).

The best way to understand them is visually

BFS search nodes level by level, starting from the root node. Then checking its children. Then children for children and so on. Until all nodes are processed or node which satisfies search condition is found.

DFS behave differently. It checks all nodes from leftmost path from the root to the leaf, then jumps up and check right node and so on.

For classic binary trees BFS implemented using Queue data structure (LinkedList implements Queue)

Dijkstra’s shortest path algorithm

A* Algorithm: It is an extension of Edsger Dijkstra’s 1959 algorithm. A* achieves better performance by using heuristics to guide its search.

What’s the difference between a Graph and a Tree?

A tree is a special type of graph, i.e., a minimal graph, where there is only one path between two vertices.

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Insertion Sort

K’th Smallest/Largest Element in Unsorted Array

Quick Select: This is an optimization. If QuickSort is used as a sorting algorithm in first step. In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.

Code: