🗂️
Data Structures
  • Data Structures Manual
  • Arrays
    • Array ADT
    • Linear Search
    • Binary Search
    • Some More Basic Operations
    • Reversing an Array
    • Operations in a Sorted Array
    • Merging Two Arrays
    • Set Operations
    • Finding Missing Elements
    • Duplicates in an Array
    • Getting a Pair whose Sum = K
    • Finding Max & Min in Single Scan
  • Strings
    • Finding the Length of a String
    • Changing Cases in a String
    • Finding Number of Vowels, Consonants & Words
    • Reversing a String
    • Checking for Palindrome
    • Duplicates in a String
    • Checking if Strings are Anagrams
    • Permutations of a String
  • Singly Linked List
    • Displaying the Nodes
    • Counting the Nodes
    • Sum of all Nodes
    • Finding the Maximum Element
    • Searching in a Node
    • Inserting a Node
    • Inserting a Node in Sorted List
    • Deleting a Node
    • Checking if List is Sorted
    • Removing Duplicates from a List
    • Reversing a Linked List
    • Concatenating Two Lists
    • Detecting a Loop in Linked List
    • Merge Two Sorted Lists
    • Finding the Middle Node
  • Cirular Linked List
    • Displaying the Nodes
    • Inserting a Node
    • Deleting a Node
  • Doubly Linked List
    • Inserting a Node
    • Deleting a Node
    • Reversing a Doubly Linked List
    • Circular Doubly Linked List
  • Stack
    • Stack Using Array
    • Stack Using Linked List
    • Balancing Parenthesis
    • Infix to Postfix
    • Evaluation of Postfix Expression
  • Queue
    • Queue using Array
    • Queue using Linked List
    • Double Ended Queue
  • Binary Tree
    • Creating a Binary Tree using Queue
    • Recursive Tree Traversals
    • Iterative Tree Traversals
    • Level Order Traversal
    • Counting Nodes in a Binary Tree
    • Finding the Height of Tree
    • Finding Sum of All Nodes
  • Binary Search Tree
    • Searching in a BST
    • Inserting in a BST
    • Deleting in a BST
  • AVL Tree
    • Inserting in an AVL Tree
    • AVL Tree Rotations
    • Deleting in an AVL Tree
  • Heap
    • Inserting in a Heap
    • Deleting in a Heap
    • Heapify
Powered by GitBook
On this page
  • Iterative Method
  • Recursive Method

Was this helpful?

  1. Arrays

Binary Search

Implementation of binary search in array using iterative as well as recursive method.

Binary search is a searching technique which is considered to be better than linear search as the array size keeps getting smaller and smaller in each iteration or recursive call and the index of found element can be found in fewer steps as compared to linear search.

Time Complexity = O(log n)

Iterative Method

int binarySearch(int a[], int low, int high, int key) {

    while (low <= high) {
    
       int mid = (low + high)/2; 
       
       if (a[mid] == key) {
           return mid;
        } else if (a[mid] > key) {
            // Key lies in the left sublist
            high = mid - 1;
        } else {
            // Key lies in the right sublist
            low = mid + 1;
        }      
    
    }
    
    return -1;

}

Recursive Method

int binarySearch(int a[], int low, int high, int key) {

    if (low <= high) {
        
        int mid = (low + high)/2;
        
        if (a[mid] == key) {
            return mid;
        } else if (a[mid] > key) {
            // Key lies in left sublist
            return binarySearch(a, low, mid-1, key);
        } else {
            // Key lies in right sublist
            return binarySearch(a, mid+1, high, key);
        }
        
    }
    
    return -1;

}

In this case, it is better to use iterative version of binary search as recursion uses internal stack. However, the time complexity remains the same for both the methods.

Contributed by Nitin Ranganath

PreviousLinear SearchNextSome More Basic Operations

Last updated 4 years ago

Was this helpful?