Program to Implement Binary Search

Program to Implement Binary Search

  • Write a program to Implement Binary Search in C
  • Write a program to Implement Binary Search in C++
  • Write a program to Implement Binary Search in Python
  • Write a program to Implement Binary Search in PHP
  • Write a program to Implement Binary Search in Java
  • Write a program to Implement Binary Search in Java Script
  • Write a program to Implement Binary Search in C#

Explanation:

An effective method for locating a target element in a sorted array is binary search. It divides the search interval in half repeatedly.

Steps of Binary Search:

  1. Initialize Pointers:
    • Set two pointers: low to the beginning of the array and high to the end of the array.
  2. Iterative or Recursive Search:
    • While the search interval is valid (low <= high):
      • Calculate the middle index: mid = low + (high – low)/2
      • Compare the target with the element at mid:
        • If the target matches the element at mid, return mid.
        • If the target is smaller than the element at mid, update high to mid – 1.
        • If the target is larger than the element at mid, update low to mid + 1.
  3. Element Not Found:
    • If low > high, the target is not in the array. Return an indicator (e.g., -1).

Program to Implement Binary Search

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // Check if target is present at mid
        if (arr[mid] == target)
            return mid;
        
        // If target is greater, ignore left half
        if (arr[mid] < target)
            left = mid + 1;
        
        // If target is smaller, ignore right half
        else
            right = mid - 1;
    }
    
    return -1;  // Element not found
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};  // Example sorted array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;  // Element to search

    int result = binarySearch(arr, size, target);
    
    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 size, int target) {
    int left = 0, right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target)
            return mid;
        
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};  // Example sorted array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;  // Element to search

    int result = binarySearch(arr, size, target);
    
    if (result != -1)
        cout << "Element found at index " << result << endl;
    else
        cout << "Element not found" << endl;

    return 0;
}

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

arr = [1, 3, 5, 7, 9, 11]  # Example sorted array
target = 7  # Element to search

result = binary_search(arr, target)

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

<?php
function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        $mid = $left + intdiv(($right - $left), 2);
        
        if ($arr[$mid] == $target)
            return $mid;
        
        if ($arr[$mid] < $target)
            $left = $mid + 1;
        else
            $right = $mid - 1;
    }
    
    return -1;
}

$arr = [1, 3, 5, 7, 9, 11];  // Example sorted array
$target = 7;  // Element to search

$result = binarySearch($arr, $target);

if ($result != -1)
    echo "Element found at index $result\n";
else
    echo "Element not found\n";
?>

public class Main {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target)
                return mid;
            
            if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};  // Example sorted array
        int target = 7;  // Element to search

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

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target)
            return mid;
        
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return -1;
}

let arr = [1, 3, 5, 7, 9, 11];  // Example sorted array
let target = 7;  // Element to search

let result = binarySearch(arr, target);

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

using System;

class Program {
    public static int BinarySearch(int[] arr, int target) {
        int left = 0, right = arr.Length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target)
                return mid;
            
            if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        
        return -1;
    }

    static void Main() {
        int[] arr = {1, 3, 5, 7, 9, 11};  // Example sorted array
        int target = 7;  // Element to search

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

List of All Programs