Description

For binary search, array must be sorted.

First compare element with the middle element.
If element matches with middle element, return mid index.

If element is greater than the middle element, then element can only present
right half subarray after the middle element.

If element is lesser than the middle element, then element can only present
left half subarray before the middle element.

C/C++

/* C Program to Search for an Element in an Array */
//Save it as BinarySearch.c

#include<stdio.h>
int main(){

    int i, n, number;

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

    int arr[n];

    printf("Enter the elements of sorted array : ");
    for(i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }

    printf("Enter the elements you want to find : ");
    scanf("%d",&number);

    int beg=0, end=(n-1), mid,found=0;
    int position = 0;

    while(beg <= end) {
        mid = ((beg+end)/2);
        if(arr[mid] == number) {
            found = 1;
            position = mid;
            break;
        }
        else {
            if(number > arr[mid]) {
                beg = mid+1;
            }
            else {
                end = mid-1;
            }
        }
    }
    if(found == 1) {
        printf("Element %d found at position %d", number, (position+1));
    }
    else {
        printf("Element %d not present in this list", number);
    }
}

Input:
Enter the no of elements of an array : 
5
Enter the elements of array : 
3
6
8
12
29
Enter the elements you want to find : 
8

Output:
Element 8 found at position 3

Java

/* Java Program to Search for an Element in an Array */
//Save it as BinarySearch.java

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
public class BinarySearch {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        
        System.out.println("Enter the no of elements of an array : ");
        int n = scanner.nextInt();
        
        int arr[] = new int[n];
        
        System.out.println("Enter the elements of sorted array : ");
        for(int i=0;i<n;i++) {
            arr[i] = scanner.nextInt();
        }
        
        System.out.println("Enter the elements you want to find : ");
        int number = scanner.nextInt();
        
        /* If element is not sorted then we can sort the array
        Arrays.sort(arr);
        */
        int beg=0, end=(n-1), mid,found=0;
        int position = 0;
        
        while(beg <= end) {
            mid = ((beg+end)/2);
            if(arr[mid] == number) {
                found = 1;
                position = mid;
                break;
            }
            else {
                if(number > arr[mid]) {
                    beg = mid+1;
                }
                else {
                    end = mid-1;
                }
            }
        }
        if(found == 1) {
            System.out.println("Element " + number+" found at "+ (position+1));
        }
        else {
            System.out.println("Element "+number+" not present in this list");
        }
    }
}

Input:
Enter the no of elements of an array : 
5
Enter the elements of array : 
3
6
8
12
29
Enter the elements you want to find : 
8

Output:
Element 8 found at position 3

Related Programs