Data Structures Questionarrie

Median of two sorted arrays of same size

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)).

Note : Since size of the set for which we are looking for median is even (2n), we need take average of middle two numbers and return floor of the average.

Time Complexity : O(n)

ALGORITHM

1) Calculate the medians m1 and m2 of the input arrays ar1[] and ar2[] respectively.
2) If m1 and m2 both are equal then we are done, return m1 (or m2)
3) If m1 is greater than m2, then median is present in one of the below two subarrays.
    a)  From first element of ar1 to m1 (ar1[0...|_n/2_|])
    b)  From m2 to last element of ar2  (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one of the below two subarrays.
    a)  From m1 to last element of ar1  (ar1[|_n/2_|...n-1])
    b)  From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays becomes 2.
6) If size of the two arrays is 2 then use below formula to get the median.
     Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

Examples :

   ar1[] = {1, 12, 15, 26, 38}
   ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 =  15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

   [15, 26, 38] and [2, 13, 17]

Let us repeat the process for above two subarrays:

    m1 = 26 m2 = 13.

m1 is greater than m2. So the subarrays become

  [15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16

Median is 5

Time Complexity : O(logn)

How is an Array different from Linked List?

The size of the arrays is fixed, Linked Lists are Dynamic in size. Inserting  and deleting a new element in an array of elements is expensive, Whereas both insertion and deletion can easily be done in Linked Lists. Random access is not allowed  in Linked Listed. Extra memory space for a pointer is required with each element of the Linked list. Arrays have better cache locality that can make a pretty big difference in performance. Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

What is Stack and where it can be used?
Stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last Out) for accessing elements. Basic operations of stack are : Push, Pop , Peek  Applications of Stack: Infix to Postfix Conversion using Stack Evaluation of Postfix Expression Reverse a String using Stack Implement two stacks in an array Check for balanced parentheses in an expression

What is a Queue, how it is different from stack and how is it implemented?

Queue is a linear structure which follows the order is First In First Out (FIFO) to access elements.  Mainly the following are basic operations  on queue: Enqueue, Dequeue, Front, Rear  The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added. Both Queues and Stacks can be implemented using Arrays and Linked Lists.

What are  Infix, prefix, Postfix notations?

Infix notation: X + Y – Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D Postfix notation (also known as “Reverse Polish notation”): X Y + Operators are written after their operands. The infix expression given above is equivalent to A B C + * D/ Prefix notation (also known as “Polish notation”): + X Y Operators are written before their operands. The expressions given above are equivalent to / * A + B C D

What is a Linked List and What are its types?

A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items – the data and a reference to the next node.Types of Linked List : Singly Linked List : In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL. For example 1->2->3->4->NULL Doubly Linked List : Here, here are two references associated with each node, One of the reference points to the next node and one to the previous node.  Eg. NULL<-1<->2<->3->NULL Circular Linked List : Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. Eg. 1->2->3->1 [The next pointer of last node is pointing to the first]

How to check if a given Binary Tree is BST or not?
If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do inorder traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false.

Linked List  -  Deleting a Node
Given a ‘key’, delete the first occurrence of this key in linked list. To delete a node from linked list, we need to do following steps. 1) Find previous node of the node to be deleted. 2) Change the next of previous node. 3) Free memory for the node to be deleted.

// A complete working Java program to demonstrate deletion in singly linked list class LinkedList { Node head; // head of list /* Linked list Node*/ class Node{ int data; Node next; Node(int d){ data = d; next = null; } } /* Given a key, deletes the first occurrence of key in linked list */ void deleteNode(int key){ // Store head node Node temp = head, prev = null; // If head node itself holds the key to be deleted if (temp != null && temp.data == key){ head = temp.next; // Changed head return; } // Search for the key to be deleted, keep track of the // previous node as we need to change temp.next while (temp != null && temp.data != key){ prev = temp; temp = temp.next; } // If key was not present in linked list if (temp == null) return; // Unlink the node from linked list prev.next = temp.next; } /* Inserts a new Node at front of the list. */ public void push(int new_data){ Node new_node = new Node(new_data); new_node.next = head; head = new_node; } /* This function prints contents of linked list starting from the given node */ public void printList() { Node tnode = head; while (tnode != null){ System.out.print(tnode.data+" "); tnode = tnode.next; } } /* Drier program to test above functions. Ideally this function should be in a separate user class. It is kept here to keep code compact */ public static void main(String[] args){ LinkedList llist = new LinkedList(); llist.push(7); llist.push(1); llist.push(3); llist.push(2); System.out.println("\nCreated Linked list is:"); llist.printList(); llist.deleteNode(1); // Delete node at position 4 System.out.println("\nLinked List after Deletion at position 4:"); llist.printList(); } }

Stack Data Structure

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). Mainly the following three basic operations are performed in the stack: Push:  Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition. Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition. Peek or Top: Returns top element of stack.  isEmpty:  Returns true if stack is empty, else false. Time Complexities of operations on stack:      push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these operations. Applications of stack: Balancing of symbols  Infix to Postfix /Prefix conversion  Redo-undo features at many places like editors, photoshop. Forward and backward feature in web browsers  Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem. Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver In Graph Algorithms like Topological Sorting and Strongly Connected Components There are two ways to implement a stack: Using array Using linked list

Implementing Stack using Arrays

/* Java program to implement basic stack operations */ class Stack {   static final int MAX = 1000;    int top;    int a[] = new int[MAX]; // Maximum size of Stack     boolean isEmpty() {      return (top < 0);    }     Stack()     {         top = -1;     }     boolean push(int x)     {         if (top >= (MAX-1))         {             System.out.println("Stack Overflow");             return false;         }         else        {             a[++top] = x;             System.out.println(x + " pushed into stack");             return true;         }     }     int pop()     {         if (top < 0)         {             System.out.println("Stack Underflow");             return 0;         }         else        {             int x = a[top--];             return x;         }     } }   // Driver code class Main {     public static void main(String args[])     {         Stack s = new Stack();         s.push(10);         s.push(20);         s.push(30);         System.out.println(s.pop() + " Popped from stack");     } }

Check for Balanced Parantheses in an expression

Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.  For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])” Algorithm: 1) Declare a character stack S. 2) Now traverse the expression string exp.       a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.       b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced. 3) After complete traversal, if there is some starting bracket left in stack then “not balanced”

Stack - Infix to Postfix

Infix expression:The expression of the form a op b. When an operator is in-between every pair of operands. Postfix expression:The expression of the form a b op. When an operator is followed for every pair of operands. Why postfix representation of the expression? The compiler scans the expression either from left to right or from right to left.  Consider the below expression:  a op1 b op2 c op3 d If op1 = +, op2 = *, op3 = + The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan. The repeated scanning makes it very in-efficient. It is better to convert the expression to postfix(or prefix) form before evaluation. The corresponding expression in postfix form is: abc*+d+.  The postfix expressions can be evaluated easily using a stack.  We will cover postfix expression evaluation in a separate post.  Algorithm 1. Scan the infix expression from left to right. 2. If the scanned character is an operand, output it. 3. Else, …..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it. …..3.2 Else, Pop all the operators from the stack which are greater than or equal to in  precedence  than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.) 4. If the scanned character is an ‘(‘, push it to the stack. 5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis. 6. Repeat steps 2-6 until infix expression is scanned. 7. Print the output 8. Pop and output from the stack until it is not empty. String exp = "a+b*(c^d-e)^(f+g*h)-i";  abcd^e-fgh*+^*+i-

Prefix to Infix Conversion

nfix : An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form (operand1 operator operand2). Example : (A+B) * (C-D) Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2). Example : *+AB-CD (Infix : (A+B) * (C-D) ) Given a Prefix expression, convert it into a Infix expression. Computers usually does the computation in either prefix or postfix (usually postfix). But for humans, its easier to understand an Infix expression rather than a prefix. Hence conversion is need for human understanding. Examples: Input : Prefix : *+AB-CD Output : Infix : ((A+B)*(C-D)) Input : Prefix : *-A/BC-/AKL Output : Infix : ((A-(B/C))*((A/K)-L)) Algorithm for Prefix to Infix:   Read the Prefix expression in reverse order (from right to left)  If the symbol is an operand, then push it onto the Stack  If the symbol is an operator, then pop two operands from the Stack      Create a string by concatenating the two operands and the operator between them.          string = (operand1 + operator + operand2)      And push the resultant string back to Stack   Repeat the above steps until end of Prefix expression.

Creating Mergeable Stack

Design a stack with following operations. a) push(Stack s, x):  Adds an item x to stack s b) pop(Stack s): Removes the top item from stack s c) merge(Stack s1, Stack s2): Merge contents of s2 into s1. Time Complexity of all above operations should be O(1).  If we use array implementation of stack, then merge is not possible to do in O(1) time as we have to do following steps. a) Delete old arrays b) Create a new array for s1 with  size equal to size of old array for s1 plus size of s2. c) Copy old contents of s1 and s2 to new array for s1 The above operations take O(n) time. We can use a linked list with two pointers, one pointer to first node (also used as top when elements are added and removed from beginning). The other pointer is needed for last node so that we can quickly link the linked list of s2 at the end of s1. Following are all operations. a) push(): Adds the new item at the beginning of linked list using first pointer. b) pop():  Removes an item from beginning using first pointer. c) merge(): Links the first pointer second stack as next of last pointer of first list. Can we do it if we are not allowed to use extra pointer? We can do it with circular linked list.  The idea is to keep track of last node in linked list. The next of last node indicates top of stack. a) push(): Adds the new item as next of last node. b) pop(): Removes next of last node. c) merge(): Links the top (next of last) of second list to the top (next of last) of first list.  And makes last of second list as last of whole list.

Find maximum depth of nested parenthesis in a String

We are given a string having parenthesis like below       “( ((X)) (((Y))) )” We need to find the maximum depth of balanced parenthesis, like 4 in above example. Since ‘Y’ is surrounded by 4 balanced parenthesis.   If parenthesis are unbalanced then return -1. Examples :  Input : S = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; Output : 4 Input : S = "( p((q)) ((s)t) )"; Output : 3 Input : S = ""; Output : 0 Input : S = "b) (c) ()"; Output : -1 Input : S = "(b) ((c) ()" Output : -1 Method 1 (Uses Stack) A simple solution is to use a stack that keeps track of current open brackets.  1) Create a stack. 2) Traverse the string, do following for every character a) If current character is ‘(’ push it to the stack . b) If character is ‘)’, pop an element. c) Maintain maximum count during the traversal. Time Complexity : O(n) Auxiliary Space : O(n) Method 2 ( O(1) auxiliary space ) This can also be done without using stack. 1) Take two variables max and current_max, initialize both of them as 0. 2) Traverse the string, do following for every character a) If current character is ‘(’, increment current_max and update max value if required. b) If character is ‘)’. Check if current_max is positive or not (this condition ensure that parenthesis are balanced). If positive that means we previously had a ‘(’ character so decrement current_max without worry. If not positive then the parenthesis are not balanced.Thus return -1. 3) If current_max is not 0, then return -1 to ensure that the parenthesis are balanced. Else return max Time Complexity : O(n) Auxiliary Space : O(1)

Design a stack with operations on middle element

How to implement a stack which will support following operations in O(1) time complexity? 1)  push() which adds an element to the top of stack. 2)  pop()  which removes an element from top of stack. 3)  findMiddle() which will return middle element of the stack. 4)  deleteMiddle() which will delete the middle element. Push and pop are standard stack operations.  The important question is, whether to use a linked list or array for implementation of stack?   Please note that, we need to find and delete middle element. Deleting an element from middle is not O(1) for array. Also, we may need to move the middle pointer up when we push an element and move down when we pop(). In singly linked list, moving middle pointer in both directions is not possible.   The idea is to use Doubly Linked List (DLL).  We can delete middle element in O(1) time by maintaining mid pointer.  We can move mid pointer in both directions using previous and next pointers.  Following is implementation of push(), pop() and findMiddle() operations. Implementation of deleteMiddle() is left as an exercise. If there are even elements in stack, findMiddle() returns the first middle element.  For example, if stack contains {1, 2, 3, 4}, then findMiddle() would return 2.

Tree Traversal - Inorder, Preorder, Postorder

Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees. Example Tree Depth First Traversals: (a) Inorder (Left, Root, Right) : 4 2 5 1 3 (b) Preorder (Root, Left, Right) : 1 2 4 5 3 (c) Postorder (Left, Right, Root) : 4 5 2 3 1 Breadth First or Level Order Traversal : 1 2 3 4 5 Please see this post for Breadth First Traversal. Inorder Traversal (Practice): Algorithm Inorder(tree) 1. Traverse the left subtree, i.e., call Inorder(left-subtree) 2. Visit the root. 3. Traverse the right subtree, i.e., call Inorder(right-subtree) Uses of Inorder In case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal s reversed can be used. Example: Inorder traversal for the above-given figure is 4 2 5 1 3. Preorder Traversal (Practice): Algorithm Preorder(tree) 1. Visit the root. 2. Traverse the left subtree, i.e., call Preorder(left-subtree) 3. Traverse the right subtree, i.e., call Preorder(right-subtree) Uses of Preorder Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on of an expression tree. Please see http://en.wikipedia.org/wiki/Polish_notation to know why prefix expressions are useful. Example: Preorder traversal for the above given figure is 1 2 4 5 3. Postorder Traversal (Practice): Algorithm Postorder(tree) 1. Traverse the left subtree, i.e., call Postorder(left-subtree) 2. Traverse the right subtree, i.e., call Postorder(right-subtree) 3. Visit the root. Uses of Postorder Postorder traversal is used to delete the tree. Please see the question for deletion of tree for details. Postorder traversal is also useful to get the postfix expression of an expression tree. Please see http://en.wikipedia.org/wiki/Reverse_Polish_notation to for the usage of postfix expression. Example: Postorder traversal for the above given figure is 4 5 2 3 1.

One more example: Time Complexity: O(n) Let us see different corner cases. Complexity function T(n) — for all problem where tree traversal is involved — can be defined as: T(n) = T(k) + T(n – k – 1) + c Where k is the number of nodes on one side of root and n-k-1 on the other side. Let’s do an analysis of boundary conditions Case 1: Skewed tree (One of the subtrees is empty and other subtree is non-empty ) k is 0 in this case. T(n) = T(0) + T(n-1) + c T(n) = 2T(0) + T(n-2) + 2c T(n) = 3T(0) + T(n-3) + 3c T(n) = 4T(0) + T(n-4) + 4c ………………………………………… …………………………………………. T(n) = (n-1)T(0) + T(1) + (n-1)c T(n) = nT(0) + (n)c Value of T(0) will be some constant say d. (traversing a empty tree will take some constants time) T(n) = n(c+d) T(n) = Θ(n) (Theta of n) Case 2: Both left and right subtrees have equal number of nodes. T(n) = 2T(|_n/2_|) + c This recursive function is in the standard form (T(n) = aT(n/b) + (-)(n) ) for master method http://en.wikipedia.org/wiki/Master_theorem. If we solve it by master method we get (-)(n) Auxiliary Space : If we don’t consider size of stack for function calls then O(1) otherwise O(n).

Binary Tree

Trees: Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are hierarchical data structures. Tree Vocabulary: The topmost node is called root of the tree. The elements that are directly under an element are called its children. The element directly above something is called its parent. For example, ‘a’ is a child of ‘f’, and ‘f’ is the parent of ‘a’. Finally, elements with no children are called leaves. tree ---- j <-- root / \ f k / \ \ a h z <-- leaves Why Trees? 1. One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer: file system ----------- / <-- root / \ ... home / \ ugrad course / / | \ ... cs101 cs112 cs113 2. Trees (with some ordering e.g., BST) provide moderate access/search (quicker than Linked List and slower than arrays). 3. Trees provide moderate insertion/deletion (quicker than Arrays and slower than Unordered Linked Lists). 4. Like Linked Lists and unlike Arrays, Trees don’t have an upper limit on number of nodes as nodes are linked using pointers. Main applications of trees include: 1. Manipulate hierarchical data. 2. Make information easy to search (see tree traversal). 3. Manipulate sorted lists of data. 4. As a workflow for compositing digital images for visual effects. 5. Router algorithms 6. Form of a multi-stage decision-making (see business chess). Binary Tree: A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. Binary Tree Representation in C: A tree is represented by a pointer to the topmost node in tree. If the tree is empty, then value of root is NULL. A Tree node contains following parts. 1. Data 2. Pointer to left child 3. Pointer to right child

Binary Tree 

Properties of Binary Tree

1) The maximum number of nodes at level ‘l’ of a binary tree is 2l-1. Here level is number of nodes on path from root to the node (including root and node). Level of root is 1. This can be proved by induction. For root, l = 1, number of nodes = 21-1 = 1 Assume that maximum number of nodes on level l is 2l-1 Since in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. 2 * 2l-1   2) Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1. Here height of a tree is maximum number of nodes on root to leaf path. Height of a tree with single node is considered as 1. This result can be derived from point 2 above. A tree has maximum nodes if all levels have maximum nodes. So maximum number of nodes in a binary tree of height h is 1 + 2 + 4 + .. + 2h-1. This is a simple geometric series with h terms and sum of this series is 2h – 1. In some books, height of a leaf is considered as 0. In this convention, the above formula becomes 2h+1 – 1   3) In a Binary Tree with N nodes, minimum possible height or minimum number of levels is  ⌈ Log2(N+1) ⌉    This can be directly derived from point 2 above. If we consider the convention where height of a leaf node is considered as 0, then above formula for minimum possible height becomes   ⌈ Log2(N+1) ⌉ – 1   4) A Binary Tree with L leaves has at least   ⌈ Log2L ⌉ + 1   levels A Binary tree has maximum number of leaves (and minimum number of levels) when all levels are fully filled. Let all leaves be at level l, then below is true for number of leaves L. L <= 2l-1 [From Point 1] l = ⌈ Log2L ⌉ + 1 where l is the minimum number of levels.   5) In Binary tree where every node has 0 or 2 children, number of leaf nodes is always one more than nodes with two children. L = T + 1 Where L = Number of leaf nodes T = Number of internal nodes with two children

Types of Binary Tree

Following are common types of Binary Trees. Full Binary Tree A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaves have two children. 18 / \ 15 30 / \ / \ 40 50 100 40 18 / \ 15 20 / \ 40 50 / \ 30 50 18 / \ 40 30 / \ 100 40 In a Full Binary, number of leaf nodes is number of internal nodes plus 1        L = I + 1 Where L = Number of leaf nodes, I = Number of internal nodes See Handshaking Lemma and Tree for proof. Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible Following are examples of Complete Binary Trees 18 / \ 15 30 / \ / \ 40 50 100 40 18 / \ 15 30 / \ / \ 40 50 100 40 / \ / 8 7 9 Practical example of Complete Binary Tree is Binary Heap. Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level. Following are examples of Perfect Binary Trees. 18 / \ 15 30 / \ / \ 40 50 100 40 18 / \ 15 30 A Perfect Binary Tree of height h (where height is the number of nodes on the path from the root to leaf) has 2h – 1 node. Example of a Perfect binary tree is ancestors in the family. Keep a person at root, parents as children, parents of parents as their children. Balanced Binary Tree A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes. For Example, AVL tree maintains O(Log n) height by making sure that the difference between heights of left and right subtrees is 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths are same and there are no adjacent red nodes. Balanced Binary Search trees are performance wise good as they provide O(log n) time for search, insert and delete. A degenerate (or pathological) tree A Tree where every internal node has one child. Such trees are performance-wise same as linked list. 10 / 20 \ 30 \ 40

Binary Search

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[]. A simple approach is to do linear search.The time complexity of above algorithm is O(n). Another approach to perform the same task is using Binary Search. 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. Example : The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n). We basically ignore half of the elements just after one comparison. Compare x with the middle element. If x matches with middle element, we return the mid index. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half. Else (x is smaller) recur for the left half.

Recursive implementation of Binary Search

/ C program to implement recursive Binary Search  #include   // A recursive binary search function. It returns  location of x in given array arr[l..r] is present,otherwise -1  int binarySearch(int arr[], int l, int r, int x)  {     if (r >= l)     {          int mid = l + (r - l)/2;          // If the element is present at the middle           // itself          if (arr[mid] == x)                return mid;          // If element is smaller than mid, then           // it can only be present in left subarray          if (arr[mid] > x)               return binarySearch(arr, l, mid-1, x);          // Else the element can only be present          // in right subarray          return binarySearch(arr, mid+1, r, x);     }     // We reach here when element is not present in array     return -1;  }     int main(void)  {     int arr[] = {2, 3, 4, 10, 40};     int n = sizeof(arr)/ sizeof(arr[0]);     int x = 10;     int result = binarySearch(arr, 0, n-1, x);     (result == -1)? printf("Element is not present in array")                   : printf("Element is present at index %d", result);     return 0;  }  ime Complexity: The time complexity of Binary Search can be written as T(n) = T(n/2) + c The above recurrence can be solved either using Recurrence T ree method or Master method. It falls in case II of Master Method and solution of the recurrence is . Auxiliary Space: O(1) in case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space.