Binary Search - a complete snapshot

696 views

A binary search is a divide and conquer search algorithm which works by comparing an input value to the middle element of the array. Based on the comparison of the input with the middle element we decide if the element is equal or less or more. If less we continue the same algorithm in the left subarray if more then right Subarray. See the following figure which describes the binary search algorithm in the pictorial way.

Algorithm

Algorithm is quite simple onecan try recursive or iterative as both are pretty straight -

get the middle element;
if the middle element equals to the searched value, the algorithm stops; otherwise, two cases are possible:
a. searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
b. searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

Recursive Code (in C)

int binary_search(int array[], int value, int left, int right) {
      int middle;

      if (left > right)
            return -1;

      middle = (left + right) / 2;

      if (array[middle] == value)
            return middle;
      else if (array[middle] > value)
            return binary_search(array, value, left, middle - 1);
      else
            return binary_search(array, value, middle + 1, right);           
}

Iterative Code (in C)

int binary_search(int arr[], int value, int left, int right) {
      while (left <= right) {
            int middle = (left + right) / 2;
            if (arr[middle] == value)
                  return middle;
            else if (arr[middle] > value)
                  right = middle - 1;
            else
                  left = middle + 1;
      }
      return -1;
}

Performance(Complexity) of Binary Search

Worst Case: o[Log (n)] --base 2
Average Case: o[Log (n)] -- base 2

posted Jun 9, 2014 by Salil Agrawal

Promote This Article

according to the time and space complexity which algorithm will be best.

commented Jun 11, 2014 by Kamini Kumari

Can u ask a fresh question probably with more detail so that I can try to respond.

commented Jun 11, 2014 by Salil Agrawal

my Question is that if i have both option like recursive and iterative ,which one will be efficient according to time and space complexity.recursive function always takes extra stack space than iteration,which i should prefer for efficient programming algorithm.

commented Jun 11, 2014 by Kamini Kumari

Will you like to post it at http://tech.queryhome.com/ask so that multiple people provides attention to your query.

commented Jun 11, 2014 by Salil Agrawal

And short answer to you query, interative approach is faster then recursion however time complexity is the same. In the recursion OS need to push the function context and pop it later which is time and space consuming a bit.

From DS point of view Time complexity is same where space complexity is higher for recursive approach.

commented Jun 11, 2014 by Salil Agrawal

Binary Search Tree - A Summary

A binary search tree (BST) binary tree data structure where each node has a comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right sub-tree.

Many a times binary tree and binary search tree looks same but they are not: a binary tree is a tree where each node has up to two leaves. In a binary tree, a left child node and a right child node contain values which can be either greater, less, or equal to parent node. But in Binary Search Tree each left child contains the value less then the parent node and each right child contains the value greater then Parent.

Balanced Binary Search Tree

Unbalanced Binary Search Tree

Sample C Implementation (Only functions)

typedef struct BST
{
    int data;
    struct BST *lchild,*rchild;
}node;

void insert(node *root,node *new_node)
{
  if(new_node->data < root->data)
     {
     if(root->lchild==NULL)
         root->lchild = new_node;
     else
         insert(root->lchild,new_node);
     }

  if(new_node->data > root->data)
     {
     if(root->rchild==NULL)
         root->rchild=new_node;
     else
         insert(root->rchild,new_node);
     }
}

node *search_recursive(node *root,int key)
{
    if (root == null) 
        return null;

    if (root->data == key)
        return node
    else 
    {
     if (key < root->data) then
        return search_recursive(root->lchild, key);
     else
        return search_recursive(root->rchild, key);
    }
}

node *search_iterative(node *root,int key)
{
 node *temp;
 temp=root;
    while(temp!=NULL)
    {
      if(temp->data==key)
         {
         return temp;
         }

      if(temp->data>key)
         temp=temp->lchild;
      else
         temp=temp->rchild;
    }
 return NULL;
}

Complexity

        Average    Worst
Space     O(n)      O(n)
Search  O(log n)    O(n)
Insert  O(log n)    O(n)
Delete  O(log n)    O(n)

Cousin of a Node in Binary Search Tree

What is a Cousin of a Node

Cousin of a node is a node or nodes which are at the same level but dont share the same parent. See the following image in which 12, 23, 54 and 76 are at the same level in which we can say 54 and 76 are the cousins of the node 12. Similarly 19 and 67 are the cousins of 9 and 14.

How to find the cousins of the Node

Logic is very simple you need to find out the level of given node and its parent. Once you know the parent the job is easy i.e. traverse each node and check its level if level is same as given node level and its parent is not same as given node then its cousin or not.

Code in C++

(picked from one of my old post)

using namespace std; 

struct node{ 
    struct node* left; 
    struct node* right; 
    int data; 
}; 

using namespace std; 

struct node{ 
    struct node* left; 
    struct node* right; 
    int data; 
}; 

// Traverse the tree in a way so that you can preserve the level and compare it with given level
void inorder(struct node* root,int present_level,int level,struct node* parent) 
{ 
  if(root!=NULL) 
  { 
   if(parent!=root) 
       inorder(root->left,present_level+1,level,parent); 
   if(level==present_level) 
       cout<<root->data<<" "; 
   if(parent!=root) 
       inorder(root->right,present_level+1,level,parent); 
  } 
} 

void make_tree(struct node **root,int data) 
{ 
    if((*root)==NULL) 
    { 
        (*root)=new node; 
        (*root)->left=NULL; 
        (*root)->right=NULL; 
        (*root)->data=data; 
        return; 
    } 
    else 
    { 
        if (((*root)->data)< data)
            make_tree(&((*root)->right),data); 
        else 
            make_tree(&((*root)->left),data); 
    } 


} 

int height(struct node* node) 
{
   if (node==NULL) 
       return 0;
   else
   {

       int lDepth = height(node->left);
       int rDepth = height(node->right);

       /* use the larger one */
       if (lDepth > rDepth) 
           return(lDepth+1);
       else return(rDepth+1);
   }
} 

void print_level(node *root, int space, int level, int currlevel)
{
    int i =0;
    if ( currlevel == level )
    {
            for (i = 0; i < space; i++)
                    printf(" ");

            if (root == NULL)
                    printf(" ");
            else
                    printf("%d",root->data);

            for (i = 0; i < space; i++)
                    printf(" ");

    }
    else
    {
            if(!root)
            {
                    print_level(NULL, space, level, currlevel + 1);
                    print_level(NULL, space, level, currlevel + 1);
            }
            else
            {
                    print_level(root->left, space, level, currlevel + 1);
                    print_level(root->right, space, level, currlevel + 1);
            }
    }
}

void print_tree(node *tree)
{
    int hght = height(tree);
    int width = (1 << ( hght + 1)) - 1;
    int space = width / 2; int i;
    for (i = 1; i <= hght; i++)
    {
            print_level(tree, space, i, 1);
            printf("\n\n");
            space = space / 2;
    }
}

struct node* find_level_and_parent(struct node* root,int data,int* level) 
{ 
    struct node* parent=NULL; 
    struct node* child=root; 

    while(1) 
    { 
        if(child==NULL) 
            return NULL; 
        if(child->data==data) 
        { 
            return parent; 
        } 
        if(data>child->data) 
        { 
            parent=child; 
            child=child->right; 
            *level=*level+1; 
        } 
        else if(data<=child->data) 
        { 
            parent=child; 
            child=child->left; 
            *level=*level+1; 
        } 
    } 
} 

int main() 
{ 
    struct node* root=NULL; 
    make_tree(&root,50); 
    make_tree(&root,17); 
    make_tree(&root,72); 
    make_tree(&root,12); 
    make_tree(&root,23); 
    make_tree(&root,34); 
    make_tree(&root,54); 
    make_tree(&root,76); 
    make_tree(&root,9); 
    make_tree(&root,14); 
    make_tree(&root,19); 
    make_tree(&root,67); 

    print_tree(root);

    int level=0; 
    struct node* temp=find_level_and_parent(root,12,&level); 

    if(temp!=NULL) 
    { 
        inorder(root,0,level,temp);
        return 0; 
    } 

    return 1; 
}

Binary Search - a complete snapshot

Algorithm

Recursive Code (in C)

Iterative Code (in C)

Performance(Complexity) of Binary Search

Your comment on this post:

Related Articles

Sample C Implementation (Only functions)

Complexity

What is a Cousin of a Node

How to find the cousins of the Node

Code in C++