Searching is a big topic in Computer Science, The high efficiency of Searching is very important. Here we will talk about some kind of data structure and algorithm to do searching for high efficiency.

Binary Search

So here, Suppose we have a sorted array and we want to find an value in this array, how could we do that? The straightforward approach is that we iterate the array and compare each element in this array, here is the code:

function search(arr, val){
  for(let i = 0; i < arr.length; i++){
    if( arr[i] === val)
      return i;
  }
}

The time complexity is O(n), if the size of the array is very large, this algorithm will run very slow. How can we do it in an efficient way? In the beginning, we assumed that the array is sorted, so at first, we get an element in the middle of the array. If the middle element is larger than the value, that means the all of the left side elements are smaller than the value, we should search it in the right side, otherwise, we should search it in the left side. Here is a picture to show the process.

Suppose we are going to find the value “4” and we search in the middle of the array each time. At first, the middle element is 7 and 4 < 7, so we search on the left side. Next, we search the middle element of the left side, the value is 3 and 4>3, so we search on the right side and do the same step. Finally, we find the value 4. Here is the implementation of the algorithm.

function search(arr, value){
  let left = 0;
  let right = arr.length-1
  while( left <= right){
    let middle = parseInt((left + right)/2)
    if( arr[middle] > value)
      right = middle - 1
    else if( arr[middle] < value)
      left  = middle + 1
    else
      return middle
  }
  return -1
}

Binary Search Tree

Before we talk about Binary Search Tree, I will introduce a data structure: Binary Tree. A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. Here is a binary tree:

The node of the value 2 is the tree’s root and it has two child, left child’s value is 7 and the right child’s value is 5 and so on. If the left child’s value is always less than the parent’s value and right child’s value is always larger than the parent’s value, it is called binary search tree. Here is a binary search tree:

When we are going to search a value in the binary search tree, we will compare the value to the current node’s value, if the value is larger than it, we will search in the right child, otherwise, we will search in the left child. Here is the code:

function search(root, val){
  if( !root ) return
  if( root.val === val )
    return root;
  if( root.val > val )
    return search(root.left, val)
  if( root.val < val)
    return search(root.right, val)
}

In general situation, the time complexity of searching operation is O(log(N)) and the worst case time complexity is O(N), why? Here is the worst case binary search tree.

All of the child at the right side, the height of the tree is N, and the search time complexity is O(N). The tree is unbalanced. What is unbalanced? For each node, if a difference between the height of the left child and the height of the right child is larger than one that is unbalanced.

If we can make the tree always to be self-balancing, the searching time complexity will always be O(log(N)).

AVL-Tree

There are two common ways to implement the self-balancing tree, one is AVL-Tree, the other is Red-Black-Tree. Here we only discuss AVL-Tree.

Each node in an AVL tree store the height of the subtrees rooted at this node. We check for each node that the height of the left subtree and the height of the right subtree differ by no more than one. This prevents situations where the tree gets too lopsided.

balance(n) = n.left.height - n.right.height

      -1 <= balance(n) <= 1

And when it is unbalanced, we can do some rotation operation to make it to balanced. If you are interested in rotation operation, here is an article to explain rotation AVL rotation

Source

Wiki Binary Search

Wiki Binary Search Tree

Binary Search Tree Algorithm

Cracking the Code Interview Pg637 AVL-TREE