Binary Search Program Using Recursion in C, C++

6 comments
Write a C, C++ code to implement binary search program using recursion.

 What is Binary Search? 

Binary Search algorithm is used to search an element in a sorted array. Binary search works by comparing the value to the middle element of an array. If the value is found then index is returned otherwise the steps is repeated until the value is found.

It is faster than linear search.

Time complexity of Linear search is O(n).

Time complexity of Binary search is O(log(n)).

What is Recursion? 

In recursion, the function call itself until the base condition is reached.  If you are not familiar with recursion then check the difference between recursion and iteration.

Reverse a number using recursion.

In my previous post we have implemented binary search using iterative approach. In this post. we are going to implement binary search using recursion.

Implement Binary Search Using Recursion in C


#include <stdio.h>
#include <stdlib.h>

void BinarySearch(int arr[],int num,int first,int last){
   
   int mid;

   if(first > last){
       
        printf("Number is not found");
        
   } else {
       
      /* Calculate mid element */
      mid = (first + last)/2;
    
      /* If mid is equal to number we are searching */

      if(arr[mid]==num){
          
            printf("Element is found at index %d ",mid);
            exit(0);
            
        }else if(arr[mid] > num){
            
            BinarySearch(arr, num, first, mid-1);
        
        }else{
            
            BinarySearch(arr, num, mid+1, last);
        }   
    }  
}


main(){

   int arr[100],beg,mid,end,i,n,num;

   printf("Enter the size of an array ");
   scanf("%d",&n);

   printf("Enter the values in sorted sequence \n");

   for(i=0;i<n;i++)
   {   
       scanf("%d",&arr[i]);
   }   


   beg=0;
   end=n-1;

   printf("Enter a value to be search: ");
   scanf("%d",&num);

   BinarySearch(arr,num,beg,end);

}

Implement Binary Search using Recursion in C++


#include <iostream>
using namespace std;

int BinarySearch(int arr[], int num, int beg, int end)
{
 int mid;
 
 if (beg > end){
  
  cout << "Number is not found";
  return 0;
  
 } else {
  
  mid = (beg + end) / 2;
  
  if(arr[mid] == num){
   
   cout << "Number is found at " << mid << " index \n";
   return 0;
  
  } else if (num > arr[mid]) {
   
   BinarySearch (arr, num, mid+1, end);
   
  } else if (num < arr[mid]) {
   
   BinarySearch (arr, num, beg , mid-1);
  }
 }
 
 
}
 
int main() {
 
 int arr[100], num, i, n, beg, end;
 
 cout <<"Enter the size of an array (Max 100) \n";
 cin >> n;
 
 cout <<"Enter the sorted values \n";
 
 for(i=0; i<n; i++) {
  
  cin >> arr[i];
 }
 
 cout <<"Enter a value to be search \n";
 cin >> num;
 
 beg = 0;
 end = n-1;
 
 BinarySearch (arr, num, beg, end);
 
 return 0;
}


Output :


Enter the size of an array (Max 100) : 6
Enter the sorted values :  2   4   6   7   8   9
Enter a value to be search :  7
Number is found at 3 index 
Read More

C Program to Implement a Stack Using Array

Leave a Comment
Write a C program to implement a stack using array. In this tutorial, You are going to learn the implement of stack data structure using an array.

What is a Stack Data Structure?

A Stack is a data structure in which insertion and deletion can be done from one end only. That's why it is also called LIFO(Last In First Out).

In stack, Insertion and deletion operation is known as push (Insertion) and pop (Deletion). While inserting and deleting an element in a stack we need to check some conditions.

For insertion, we need to check whether a memory is available, if memory is not available then it is known as stack overflow. Similarly, while deleting (pop operation) an element, if no element is present in a stack, then it is known as stack underflow.


C Program to Implement a Stack Using Array



Reverse a String using Stack

C Program to Implement a Stack using Array


Let's write a c code to implement stack push and pop operation using an array.


#include <stdio.h>

#define MAX 50
int top=-1;
int arr[MAX];

void push(int item){
     
    if(top==MAX-1){
        printf("Stack Overflow");
        return;
    }else{
        //Insert the element in a stack
        arr[++top]=item;
        printf("Value inserted in stack is %d\n",item);
    }
}

void pop() {

    int val;

    if(top==-1){
        printf("Stack underflow");
        return;
    }else{
        val = arr[top];
        --top;
    }

    printf( "Value deleted from stack is %d\n",val);
}

main()
{
    
    //Inserting value in stack

    push(5);
    push(7);
    push(2);

    //Deleting value from stack

    pop();
    pop();

} 


Stack Program in C using Array - Video Tutorial




Stack push and pop operation

Read More

Write a Program to Reverse a String Using Stack

19 comments

Write a C, C++ program to reverse a string using Stack data structure. In this question, A string is input by a user and our program will reverse a string using a Stack.

Stack Data Structure


Stack is an abstract data type in which push (insertion) and pop (deletion) operations can be done at one end.  Stack is a LIFO (Last in First Out) data structure, which means element which is inserted at last must be the first one to be removed.

Some important articles regarding Stack data structure and it's implementation.


Stack program in C using an Array

Implement Stack data structure

Stack implementation using Linked List

MCQ on stack and queue for practice

Reverse a string using for and while loop


Program to Reverse a String Using Stack Data Structure



#include <stdio.h>
#include <string.h>

#define max 100
int top,stack[max];


void push(char x){

      // Push(Inserting Element in stack) operation
      if(top==max-1){
          printf("stack overflow");
      }  else {
          stack[++top]=x;
      }  

}

void pop(){

    

    // Pop (Removing element from stack)
          
      printf("%c",stack[top--]);
}


main()
{

   char str[]="I Love Programming";

   
   int len = strlen(str), i;

   
   for(i=0; i<len; i++)
        push(str[i]);

    
   for(i=0; i<len; i++)    
      pop();        
}


Output

gnimmargorP evoL I





Programming questions on String


C++ Program to Reverse a String using Stack


#include <iostream>
#include <string.h>
#include <stack> // Standard library for creating stack

using namespace std;

void reverse(char *str, int len)
{
 stack<char> s;
 int i;
 
 // Push into a stack
 for(i = 0; i < len; i++)  
  s.push(str[i]);
 
 // Pop from a stack   
 for(i= 0; i < len; i++)
 {
  str[i] = s.top();
  s.pop();
 }
 
}

int main()
{

   char str[]="I Love Programming";
   int len = strlen(str);
   
   reverse(str, len);
   
   cout <<"After reversing a string \n" << str;
   
   return 0;
}




C, C++ interview questions
Read More

C Program to Calculate the Sum of First N Natural Numbers

1 comment
Write a C program to calculate the sum of first n natural numbers. Given an input n, We have to write a code to print the sum of first n natural number (1 to n).

There are multiple approaches to solve this problem.

* We can solve this problem using loop.
* Other approach is to use mathematical formula to calculate the sum of first n natural number.
* We can also use recursion to find the sum of first n natural numbers using recursion.

Suppose if user has entered a number 10. So, we have to calculate the sum of first 10 numbers ( 1 to 10). The Sum of first 10 numbers is 55.

Program to Calculate Sum of Digits of a Number

How to Calculate the Sum of first N Natural Numbers


1. First approach is to use for loop to calculate the sum of first n natural numbers.

  for(i=1; i<=num; i++){

      sum +=i;
  }

 
Program to Count Number of Words in a Sentence by Taking Input from User

2. Another approach is to use mathematical formula n(n+1)/2 to calculate the sum of first n natural numbers.

Suppose, If user has entered the value of n is 20 = 20 * (20 + 1)/2 = 210

The sum of first 20 numbers is 210.

C Program to Calculate the Sum of N Natural Numbers


C, C++ Interview Questions.

C Program to Calculate the Sum of First n Natural Numbers using Mathematical Formula


We have discussed multiple approaches to calculate the sum of first n natural numbers. Let's write a code to solve this problem using discussed approaches.

In this approach, we are calculating the sum of first n natural numbers using mathematical formula.

#include <stdio.h>

int main()
{

    int n,sum;

    printf("Enter the value of n");
    scanf("%d",&n);

    sum = (n*(n+1))/2;

    printf("The sum of n number is %d",sum);
    
    return 0;

}

C Program to Calculate Sum of First n Natural Numbers using For Loop


#include <stdio.h>

int main(void) {
 
 
    int n,sum=0,i;

    printf("Enter the value of n");
    scanf("%d",&n);
    
    /* Iterate from 1 to n . */

    for(i=1; i<=n; i++) {
     
     sum = sum + i;
    }
    
    printf("The sum of n number is %d",sum);
    
    return 0;
}


Find the Sum of First N Odd Numbers

Output:

Enter the value of n : 10

The sum of n number is : 55



Programming questions on Strings

Programming questions on Recursion

Programming questions on Array

Programming questions on Linked List
Read More

Java Program to Reverse an Array using Recursion

Leave a Comment
Write a java program to reverse an array using recursion. Given an input array, we have to write a java code to reverse an array using recursion. In this tutorial, We are going to solve this problem using recursion.

Recursion is an important programming concept, if you are not familiar with recursion concept then you can check this tutorial on recursion.

Difference between recursion and iteration

Recursion objective questions for practice

Java program to reverse an array using iteration


Java program to reverse an array using recursion



Java Program to Reverse an Array using Recursion


Let's write a java code to reverse an array using recursion.


import java.util.Scanner;

public class ReverseArrayRecursion {

  public static void reverse(int arr[], int start, int end) {

      int temp;

      //If start index is greater than end index
      if(start >= end)
        return;

      //Logic to swap values
      temp = arr[start];
      arr[start] = arr[end];
      arr[end] = temp;

      //Recursively call
      reverse(arr, start+1, end-1);
   }


  public static void main(String[] args) {

       Scanner in = new Scanner(System.in);

       System.out.println("Enter the size of an array");
       int n = in.nextInt();

       //Declare an array
       int arr[] =  new int[n];

       System.out.println("Enter an array values");
        
       //Input array values
       for(int i = 0; i < n; i++) {
          arr[i] = in.nextInt();
       }

       reverse(arr, 0, n-1);
       
       System.out.println("Reverse of an array is ");

       for(int i = 0; i < n; i++) {
          System.out.println(arr[i]);
       }
  }

}



Java program to reverse an array using recursion - Video Tutorial


Read More

Java Program to Check Perfect Number

Leave a Comment
Write a java program to check whether a number is perfect or not. Given an input number, we have to write a java code which check whether an input number is perfect number or not.

Before solving this problem, let's first understand what is a perfect number.

What is Perfect Number?


A perfect number is a positive integer that is equal to the sum of it's positive divisors  excluding the number itself.

For example -

6  is a perfect number. It's positive divisor is 1, 2 and 3 and sum of it's positive divisor is 6 (1 + 2 + 3).

Similarly, 28 is a perfect number. Sum of the positive divisor is 28 (1 + 2 + 4 + 7 + 14).

10 is not a perfect number. Sum of the positive divisor of 10 is 8 ( 1 + 2 + 5).

Java Program to Check Perfect Number



Java Program to Convert Binary to Decimal Number

Java program to find second smallest number in an array

Java Programming Questions with Answers




Java Program to Check Perfect Number or Not


We have discussed what is a perfect number? Let's write a java code which takes an input number and check whether an input number is a perfect number or not.


package perfectnumber;

import java.util.*;

public class PerfectNumber {

    public static void main(String[] args) {

        int num, sum = 0;
        
        System.out.println("Enter a number");
            
        Scanner in = new Scanner(System.in);
        num = in.nextInt();
            
        /* If number is greater than zero */
        if (num > 0) {

          for (int i = 1; i < num; i++) {

            /* sum of it's factors */
            if ( num % i == 0) {
                sum = sum + i;
            }
        }
    
          if ( sum == num) {
              System.out.println(num + " is a perfect number ");

          } else {
              System.out.println (num + " is not a perfect number ");
          }
            
       }   else {
                
            System.out.println (" Please enter positive number ");
       }
   }
    
}




Output : 

Enter a number  :    28

28 is a perfect number

Sorting algorithms and their time complexity
Read More

C++ Program to Insert an Element in an Array

Leave a Comment
Write a c++ program to insert an element in an array. In this program, we are going to write a c++ code which takes an input array, position and value of an element and insert it an array.


C program to insert an element in an array


C++ Program to Insert an Element in an Array



C++ Program to Insert an Element in an Array


#include <iostream>
using namespace std;

 int main() {
 
   int arr[100], size, pos, val, i, temp;
 
   cout << "Enter the size of an array (MAX 100) \n";
   cin  >> size;
 
   // Create an input array
   cout << "Enter an elements in an array \n";
 
   //Input the value of an array
   for(i = 0; i < size; i++) {
      cin >> arr[i];
   }
 
   // Take a position of a new element
   cout << "Enter a position\n";
   cin  >> pos;
 
   //Input value of an element to be inserted
   cout << "Enter a value to insert\n";
   cin  >> val;
 
   //Shift element by one position
   for(i = size; i >= pos; i--) {
      arr[i] = arr[i-1];
   }
 
   //Increase the length of an array
   size++;
 
   //Insert new value in an array
   arr[pos-1] = val;
 
   cout << "Array after inserting a new value \n";
 
   for(i = 0; i < size; i++) {
      cout << arr[i] << " ";
   }
 
 
   return 0;
 }



C++ code for practice
Read More