Skip to content
  • Facebook
GeekCer Logo

GeekCer

The geek's Coding education and Review centre

  • Home
  • Tutorials
    • Java
    • Servlet
    • JSP
    • Python
    • C Tutorial
    • Spring
    • Spring Boot
    • MongoDB
    • Hibernate
    • Data Structure
  • General Knowledge
  • Biography
  • Grammar
  • Festival (त्योहार)
  • Interview
  • Differences
  • Important
  • Toggle search form

Home » Data Structure » Binary search algorithm in C, Recursive, Iterative, examples

  • List Of National Animals Of Countries
    List Of National Animals Of Countries General Knowledge
  • Ayodhya Kand in Hindi | अयोध्या काण्ड | राम को 14 वर्ष का वनवास
    Ayodhya Kand in Hindi | अयोध्या काण्ड | राम को 14 वर्ष का वनवास Spiritual
  • Diwali The Festival of Lights
    Diwali 2022, Indian Festival of Lights essay (दिवाली त्योहार पर निबंध, कहानी) Festival
  • Draupadi Murmu Biography In Hindi | द्रौपदी मुर्मू की जीवनी
    Draupadi Murmu Biography In Hindi | द्रौपदी मुर्मू की जीवनी Biography
  • Sunder Kand in Hindi | Hanuman Kand | हनुमान जी का सुंदरकांड
    Sunder Kand in Hindi | Hanuman Kand | हनुमान जी का सुंदरकांड Spiritual
  • Ramayan : Short Story of ramayana in Hindi | Qualities of Rama
    Ramayan : Short Story of ramayana in Hindi | Qualities of Rama Spiritual
  • Ganesh Chaturthi Puja in Hindi | गणेश चतुर्थी का व्रत, महत्व, कथा
    Ganesh Chaturthi Puja in Hindi | गणेश चतुर्थी का व्रत, महत्व, कथा Festival
  • Ramayana Uttar Kand Luv Kush| रामायण उत्तर कांड इन हिंदी
    Ramayana Uttar Kand Luv Kush | रामायण उत्तर कांड इन हिंदी Spiritual

Binary search algorithm in C, Recursive, Iterative, examples

Posted on April 9, 2022April 9, 2022 By GeekCer Education No Comments on Binary search algorithm in C, Recursive, Iterative, examples
Binary search in Data structures In C (Recursive and Iterative)

If you have a sorted array, binary search algorithm is the quickest way. In a sorted array or list, binary search is used to increase the speed of the search operation.

You might be wondering why we would want to arrange the array in that particular order? The benefit of structuring the array is that it greatly reduces the search time.

When compared to Linear Searching, Binary Searching is much faster because the binary search reduces the number of iterations .

Table of Contents

  • Working of binary search
  • Program of Binary Search using iterative way
  • Program of Binary Search using recursive way
  • Time Complexities of Binary Search
  • Space Complexity of Binary Search
  • Advantages of Binary Search Algorithm
  • Disadvantages of Binary Search Algorithm

Working of binary search

We can implement Binary Search Algorithm in two ways.

  • Iterative Way
  • Recursive Way

How does Binary Search Work? In binary search, we locate the key element by using the element that is nearly in the middle of the array. The search is successful if a match is found.

If we don’t find the element, we search for the main element in a similar manner, either in the top or bottom half of the array.

If array is in ascending order : The search will continue on the lower half of an array if the array is in ascending order and the key element is smaller than the middle element. The search will continue at the upper half of an array if the key element is greater than the middle element.

If array is in descending order : The search will continue on the lower half of an array if the array is in descending order and the key element is greater than the middle element. The search will continue at the upper half of an array if the key element is less than the middle element.

Program of Binary Search using iterative way


#include <stdio.h>

#define MAX 8
int main() {
  int array[MAX] = {
    10,
    20,
    30,
    36,
    50,
    60,
    65,
    80
  };
  int keyElement = 65;
  int first, last, middle;

  first = 0;
  last = MAX - 1;
  middle = (first + last) / 2;

  while (first <= last) {
    if (array[middle] < keyElement) {
      first = middle + 1;
    } else if (array[middle] == keyElement) {
      printf("%d is found at %d location.\n", keyElement, middle + 1);
      break;
    } else {
      last = middle - 1;
    }
    middle = (first + last) / 2;
  }
  if (first > last)
    printf("%d is not available in the array.\n", keyElement);

  return 0;
}

Output:
65 is found at 7 location.

Program of Binary Search using recursive way


#include <stdio.h>

#define MAX 8
int main() {
  int array[MAX] = {
    10,
    20,
    30,
    36,
    50,
    60,
    65,
    80
  };
  int keyElement = 36;
  int first, last, middle, index;

  first = 0;
  last = MAX - 1;

  index = binarySearch(array, keyElement, first, last);
 
  if (index == -1) {
    printf("%d is not available in the array.\n", keyElement);
  }
  else {
   printf("%d is found at %d location.\n", keyElement, index + 1);
  }
  return 0;
}

int binarySearch(int array[], int keyElement, int first, int last) {
  if (last >= first) {
    int mid = first + (last - first) / 2;

    // If found at mid, then return it
    if (array[mid] == keyElement)
      return mid;

    // Search the first half
    if (array[mid] > keyElement)
      return binarySearch(array, keyElement, first, mid - 1);

    // Search the second half
    return binarySearch(array, keyElement, first + 1, last);
  }

  return -1;
}

Output:
36 is found at 4 location.

Also Read: Bubble Sort in Data Structure

Time Complexities of Binary Search

In binary search, the number of comparisons will be needed to find an search element in a array or list will not more than O(log n), where n is the number of elements in the list or array. As a result, the binary search technique has a time complexity of O(n *(log n).

  • Worst case complexity: O(log n)
  • Average case complexity: O(log n)
  • Best case complexity: O(1)

Space Complexity of Binary Search

The space complexity of a binary search algorithm is affected by how the algorithm is implemented. The space complexity in the iterative technique will be O(1) and in the recursive technique will be O(log n).

Advantages of Binary Search Algorithm

  • Because binary search indicates whether to look for an element before or after the current place, it eliminates half of the array from the search by comparing the results.
  • Binary Search performs much better than linear search for large data sets.

Disadvantages of Binary Search Algorithm

  • It’s difficult to create a binary search program since it’s prone to errors.
  • Because of its random access nature, binary search has a poor memory interaction.
  • More stack space is required for the recursive technique.

Share this:

  • Click to share on Facebook (Opens in new window)
  • Click to share on WhatsApp (Opens in new window)
  • Click to share on Twitter (Opens in new window)
  • More
  • Click to share on LinkedIn (Opens in new window)
  • Click to share on Pinterest (Opens in new window)

Also Read

Data Structure

Post navigation

Previous Post: Bubble Sort Algorithm in Data Structure | Bubble Sort Example
Next Post: Linear search algorithm | Linear search program in C, Example

More Related Articles

Bubble Sort Algorithm in Data Structure | Bubble Sort Example Bubble Sort Algorithm in Data Structure | Bubble Sort Example Data Structure
Dynamic memory allocation in C, malloc, realloc, calloc and free Dynamic memory allocation in C using malloc, realloc, calloc and free Data Structure
Linear search algorithm | Linear search program in C, Example Linear search algorithm | Linear search program in C, Example Data Structure
Linked List in Data Structure and Algorithm, Types, Operations Linked List in Data Structure and Algorithm, Types, Operations C Language

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

  • National Farmers Day in Hindi | राष्ट्रीय किसान दिवस पर निबंध | चौधरी चरण सिंह जयंती
  • Human rights day in Hindi: 10 दिसंबर ह्यूमन राइट्स डे
  • Unicef day is celebrated on December 11 | Speech on unicef day
  • Indian Navy Day: जल सेना दिवस कब और क्यों मनाया जाता है?
  • P V Sindhu Biography in Hindi, Badminton, State, Caste पी. वी. सिंधु जीवन परिचय, कहानी, राज्य, जाति
  • Draupadi Murmu Biography In Hindi | द्रौपदी मुर्मू की जीवनी
  • Difference between Internet and Intranet
    Difference between Internet and Intranet Differences
  • Network kya hai (नेटवर्क क्या है)
    Network kya hai (नेटवर्क क्या है) Networking
  • TCP/IP Model, Full Form, Layers and their Functions
    TCP/IP Model, Full Form, Layers and their Functions Networking
  • Difference between TCP and UDP
    Difference between TCP and UDP | TCP vs UDP examples Differences
  • Similarities and difference between OSI and TCP/IP model
    OSI vs TCP/IP Model, Similarities and difference between OSI and TCP/IP model Networking
  • OSI Model | 7 Layers of OSI Model in Computer network
    OSI Model | 7 Layers of OSI Model in Computer network, Functions Networking
  • IPv4 Vs IPv6 | Difference between IPv4 and IPv6
    IPv4 Vs IPv6 | Difference between IPv4 and IPv6 Differences
  • Java Tutorial
  • Servlet Tutorial
  • JSP Tutorial
  • Maven Tutorial
  • HTML Tutorial
  • Programs
  • Hindi/English Grammar
  • Difference Between ... and ...
  • HR Interview
  • Important Articles

Write to Us:
geekcer.code@gmail.com

  • About Us
  • Privacy and Policy
  • Disclaimer
  • Contact Us
  • Sitemap

Copyright © GeekCer 2022 All Rights reserved