CodeCrucks

CodeCrucks

Program to Perform Binary Search using Recursion

Program to Perform Binary Search using Recursion

by · Published · Updated

  • Write a program to Perform Binary Search using Recursion in C
  • Write a program to Perform Binary Search using Recursion in C++
  • Write a program to Perform Binary Search using Recursion in Python
  • Write a program to Perform Binary Search using Recursion in PHP
  • Write a program to Perform Binary Search using Recursion in Java
  • Write a program to Perform Binary Search using Recursion in Java Script
  • Write a program to Perform Binary Search using Recursion in C#

Explanation:

An effective method for locating an element in a sorted array is binary search. Recursion-based binary search logic consists of splitting the search range in half and concentrating on the half that contains the target.

Recursive Algorithm

  1. Define a Function:
    • binarySearch(arr, low, high, key)
    • Input parameters:
      • arr: The sorted array.
      • low: The starting index.
      • high: The ending index.
      • key: The element to search for.
  2. Base Case:
    • If low > high, return -1.
  3. Recursive Case:
    • Compute the middle index: mid = (low + high) / 2.
    • Compare arr[mid] with key:
      • If equal, return mid.
      • If arr[mid] > key, search in the left half.
      • If arr[mid] < key, search in the right half.

Program to perform Binary Search using Recursion

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int key) {
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;

    if (arr[mid] == key) {
        return mid;
    } else if (arr[mid] > key) {
        return binarySearch(arr, low, mid - 1, key);
    } else {
        return binarySearch(arr, mid + 1, high, key);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key;

    printf("Enter the element to search: ");
    scanf("%d", &key);

    int result = binarySearch(arr, 0, n - 1, key);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }
    return 0;
}


#include <iostream>
using namespace std;

int binarySearch(int arr[], int low, int high, int key) {
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;

    if (arr[mid] == key) {
        return mid;
    } else if (arr[mid] > key) {
        return binarySearch(arr, low, mid - 1, key);
    } else {
        return binarySearch(arr, mid + 1, high, key);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key;

    cout << "Enter the element to search: ";
    cin >> key;

    int result = binarySearch(arr, 0, n - 1, key);
    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }
    return 0;
}


def binary_search(arr, low, high, key):
    if low > high:
        return -1
    mid = low + (high - low) // 2

    if arr[mid] == key:
        return mid
    elif arr[mid] > key:
        return binary_search(arr, low, mid - 1, key)
    else:
        return binary_search(arr, mid + 1, high, key)

arr = [1, 2, 3, 4, 5, 6, 7]
key = int(input("Enter the element to search: "))
result = binary_search(arr, 0, len(arr) - 1, key)

if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found")


<?php
function binarySearch($arr, $low, $high, $key) {
    if ($low > $high) {
        return -1;
    }
    $mid = $low + intval(($high - $low) / 2);

    if ($arr[$mid] == $key) {
        return $mid;
    } elseif ($arr[$mid] > $key) {
        return binarySearch($arr, $low, $mid - 1, $key);
    } else {
        return binarySearch($arr, $mid + 1, $high, $key);
    }
}

$arr = array(1, 2, 3, 4, 5, 6, 7);
echo "Enter the element to search: ";
$key = intval(trim(fgets(STDIN)));

$result = binarySearch($arr, 0, count($arr) - 1, $key);
if ($result != -1) {
    echo "Element found at index $result\n";
} else {
    echo "Element not found\n";
}
?>


import java.util.Scanner;

public class Main {
    public static int binarySearch(int[] arr, int low, int high, int key) {
        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) / 2;

        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] > key) {
            return binarySearch(arr, low, mid - 1, key);
        } else {
            return binarySearch(arr, mid + 1, high, key);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the element to search: ");
        int key = scanner.nextInt();

        int result = binarySearch(arr, 0, arr.length - 1, key);
        if (result != -1) {
            System.out.println("Element found at index " + result);
        } else {
            System.out.println("Element not found");
        }
    }
}


function binarySearch(arr, low, high, key) {
    if (low > high) {
        return -1;
    }
    const mid = low + Math.floor((high - low) / 2);

    if (arr[mid] === key) {
        return mid;
    } else if (arr[mid] > key) {
        return binarySearch(arr, low, mid - 1, key);
    } else {
        return binarySearch(arr, mid + 1, high, key);
    }
}

const arr = [1, 2, 3, 4, 5, 6, 7];
const key = parseInt(prompt("Enter the element to search:"));
const result = binarySearch(arr, 0, arr.length - 1, key);

if (result !== -1) {
    console.log(`Element found at index ${result}`);
} else {
    console.log("Element not found");
}


using System;

class Program {
    static int BinarySearch(int[] arr, int low, int high, int key) {
        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) / 2;

        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] > key) {
            return BinarySearch(arr, low, mid - 1, key);
        } else {
            return BinarySearch(arr, mid + 1, high, key);
        }
    }

    static void Main() {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        Console.Write("Enter the element to search: ");
        int key = int.Parse(Console.ReadLine());

        int result = BinarySearch(arr, 0, arr.Length - 1, key);
        if (result != -1) {
            Console.WriteLine("Element found at index " + result);
        } else {
            Console.WriteLine("Element not found");
        }
    }
}

List of All Programs