Software Development Exam  >  Software Development Notes  >  Basics of C++  >  Code: Binary Search

Code: Binary Search | Basics of C++ - Software Development PDF Download

Algorithm

Parameters inital_value , end_value

  • Step 1 : Find the middle element of array. using ,
  • middle = initial_value + end_value / 2 ;
  • Step 2 : If middle = element, return ‘element found’ and index.
  • Step 3 : if middle > element, call the function with end_value = middle - 1 .
  • Step 4 : if middle < element, call the function with start_value = middle + 1 .
  • Step 5 : exit.

The implementation of the binary search algorithm function uses the call to function again and again. This call can be of two types

  • Iterative call is looping over the same block of code multiple times
  • Recursive call is calling the same function again and again.

Program to Implement Binary Search Using Iterative Call

Example

#include <stdio.h>

int iterativeBinarySearch(int array[], int start_index, int end_index, int element){

   while (start_index <= end_index){

      int middle = start_index + (end_index- start_index )/2;

      if (array[middle] == element)

         return middle;

      if (array[middle] < element)

         start_index = middle + 1;

      else

         end_index = middle - 1;

   }

   return -1;

}

int main(void){

   int array[] = {1, 4, 7, 9, 16, 56, 70};

   int n = 7;

   int element = 16;

   int found_index = iterativeBinarySearch(array, 0, n-1, element);

   if(found_index == -1 ) {

      printf("Element not found in the array ");

   }

   else {

      printf("Element found at index : %d",found_index);

   }

   return 0;

}

Output

Element found at index : 4

Program to Implement Binary Search Using Recursive Call

Example:

#include <stdio.h>

int recursiveBinarySearch(int array[], int start_index, int end_index, int element){

   if (end_index >= start_index){

      int middle = start_index + (end_index - start_index )/2;

      if (array[middle] == element)

         return middle;

      if (array[middle] > element)

         return recursiveBinarySearch(array, start_index, middle-1, element);

      return recursiveBinarySearch(array, middle+1, end_index, element);

   }

   return -1;

}

int main(void){

   int array[] = {1, 4, 7, 9, 16, 56, 70};

   int n = 7;

   int element = 9;

   int found_index = recursiveBinarySearch(array, 0, n-1, element);

   if(found_index == -1 ) {

      printf("Element not found in the array ");

   }

   else {

      printf("Element found at index : %d",found_index);

   }

   return 0;

}

Output


Element found at index : 3

The document Code: Binary Search | Basics of C++ - Software Development is a part of the Software Development Course Basics of C++.
All you need of Software Development at this link: Software Development
70 videos|44 docs|15 tests
70 videos|44 docs|15 tests
Download as PDF
Explore Courses for Software Development exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Download the FREE EduRev App
Track your progress, build streaks, highlight & save important lessons and more!
Related Searches

practice quizzes

,

study material

,

Important questions

,

Viva Questions

,

Semester Notes

,

Free

,

past year papers

,

Exam

,

Code: Binary Search | Basics of C++ - Software Development

,

ppt

,

Previous Year Questions with Solutions

,

pdf

,

Extra Questions

,

Objective type Questions

,

video lectures

,

Code: Binary Search | Basics of C++ - Software Development

,

Summary

,

Sample Paper

,

MCQs

,

Code: Binary Search | Basics of C++ - Software Development

,

shortcuts and tricks

,

mock tests for examination

;