binary search (recursive) code example

Example 1: binary search program c++

#include <iostream>
using namespace std;

// This program performs a binary search through an array, must be sorted to work
int binarySearch(int array[], int size, int value) 
{   
    int first = 0,         // First array element       
    last = size - 1,       // Last array element       
    middle,                // Mid point of search       
    position = -1;         // Position of search value   
    bool found = false;        // Flag   
    while (!found && first <= last) 
    {      
        middle = (first + last) / 2;     // Calculate mid point      
        if (array[middle] == value)      // If value is found at mid      
    	{         
                found = true;         
                position = middle;      
        }      
        else if (array[middle] > value)  // If value is in lower half         
            last = middle - 1;      
        else         
            first = middle + 1;          // If value is in upper half   
    }   
    return position;
}
int main ()
{
    const int size = 5; // size initialization
    int array[size] = {1, 2, 3, 4, 5}; // declare array of size 10
    int value; // declare value to be searched for
    int result; // declare variable that will be returned after binary search

    cout << "What value would you like to search for? "; // prompt user to enter value
    cin >> value;
    result = binarySearch(array, size, value);

    if (result == -1) // if value isn't found display this message
        cout << "Not found\n";
    else  // If value is found, displays message
        cout << "Your value is in the array.\n"; 
  
    return 0;
}

Example 2: binary search java

// Java implementation of iterative Binary Search 
class BinarySearch { 
	// Returns index of x if it is present in arr[], 
	// else return -1 
	int binarySearch(int arr[], int x) 
	{ 
		int l = 0, r = arr.length - 1; 
		while (l <= r) { 
			int m = l + (r - l) / 2; 

			// Check if x is present at mid 
			if (arr[m] == x) 
				return m; 

			// If x greater, ignore left half 
			if (arr[m] < x) 
				l = m + 1; 

			// If x is smaller, ignore right half 
			else
				r = m - 1; 
		} 

		// if we reach here, then element was 
		// not present 
		return -1; 
	} 

	// Driver method to test above 
	public static void main(String args[]) 
	{ 
		BinarySearch ob = new BinarySearch(); 
		int arr[] = { 2, 3, 4, 10, 40 }; 
		int n = arr.length; 
		int x = 10; 
		int result = ob.binarySearch(arr, x); 
		if (result == -1) 
			System.out.println("Element not present"); 
		else
			System.out.println("Element found at "
							+ "index " + result); 
	} 
}

Example 3: binary search with non recursive function call

/* Binary search program in C using both recursive and non recursive functions */
 
#include <stdio.h>
#define MAX_LEN 10
 
/* Non-Recursive function*/
void b_search_nonrecursive(int l[],int num,int ele)
{
   int l1,i,j, flag = 0;
   l1 = 0;
   i = num-1;
   while(l1 <= i)
   {
      j = (l1+i)/2;
      if( l[j] == ele)
      {
    printf("\nThe element %d is present at position %d in list\n",ele,j);
         flag =1;
         break;
      }
      else
        if(l[j] < ele)
           l1 = j+1;
        else
           i = j-1;
   }
   if( flag == 0)
   printf("\nThe element %d is not present in the list\n",ele);
}
 
/* Recursive function*/
int b_search_recursive(int l[],int arrayStart,int arrayEnd,int a)
{
  int m,pos;
  if (arrayStart<=arrayEnd)
  {
    m=(arrayStart+arrayEnd)/2;
    if (l[m]==a)
      return m;
    else if (a<l[m])
      return b_search_recursive(l,arrayStart,m-1,a);
    else
      return b_search_recursive(l,m+1,arrayEnd,a);
   }
   return -1;
}
 
void read_list(int l[],int n)
{
   int i;
   printf("\nEnter the elements:\n");
   for(i=0;i<n;i++)
       scanf("%d",&l[i]);
}
 
void print_list(int l[],int n)
{
    int i;
   for(i=0;i<n;i++)
       printf("%d\t",l[i]);
}
 
/*main function*/
main()
{
   int l[MAX_LEN], num, ele,f,l1,a;
   int ch,pos;
 
   //clrscr();
 
   printf("======================================================");
   printf("\n\t\t\tMENU");
   printf("\n=====================================================");
   printf("\n[1] Binary Search using Recursion method");
   printf("\n[2] Binary Search using Non-Recursion method");
   printf("\n\nEnter your Choice:");
   scanf("%d",&ch);
 
   if(ch<=2 & ch>0)
   {
     printf("\nEnter the number of elements : ");
     scanf("%d",&num);
     read_list(l,num);
     printf("\nElements present in the list are:\n\n");
     print_list(l,num);
     printf("\n\nEnter the element you want to search:\n\n");
     scanf("%d",&ele);
 
 
   switch(ch)
   {
     case 1:printf("\nRecursive method:\n");
        pos=b_search_recursive(l,0,num,ele);
        if(pos==-1)
        {
        printf("Element is not found");
        }
        else
        {
        printf("Element is found at %d position",pos);
        }
        //getch();
        break;
 
     case 2:printf("\nNon-Recursive method:\n");
        b_search_nonrecursive(l,num,ele);
        //getch();
        break;
     }
   }
//getch();
}