Program to Perform Binary Search using Recursion
- 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
- 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.
- Base Case:
- If low > high, return -1.
- 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
-
C
-
C++
-
Python
-
PHP
-
JAVA
-
Java Script
-
C#
#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"); } } }