Binary Search Using Recursion Program in Java and Python
ISC 2015 Question 8 solution to search an admission number using recursive binary search in Java and Python.
Question:
A class Admission contains the admission numbers of 100 students. Some of the data members and member functions are given below:
Specify the class Admission giving details of the constructor, void fillArray() and int binSearch(int, int, int). Define the main() function to create an object and call the functions accordingly to enable the task.
Example
Algorithm:
Step 1: Start.
Step 2: Define a class named Admission.
Step 3: Declare an integer array Adno of size 100.
Step 4: Create a static Scanner object to accept input.
Step 5: In the constructor, initialize all elements of Adno to 0.
Step 6: In fillArray(), accept 100 admission numbers into Adno.
Step 7: Sort the array in ascending order using nested loops and swapping.
Step 8: In binSearch(l, u, v), if u < l, return -1.
Step 9: Calculate the middle position as mid = (l + u) / 2.
Step 10: If v == Adno[mid], return 1.
Step 11: If v > Adno[mid], recursively search the right half using binSearch(mid + 1, u, v).
Step 12: Otherwise, recursively search the left half using binSearch(l, mid - 1, v).
Step 13: In main(), create an object of Admission.
Step 14: Call fillArray(), accept the admission number to be searched and call binSearch(0, 99, v).
Step 15: If the returned value is 1, display that the admission number is found; otherwise display that it is not found.
Step 16: Stop.
Explanation:
Binary search is an efficient searching technique used on a sorted array. The class Admission stores 100 admission numbers in the array Adno. The constructor initializes every array element to 0 so that the array starts with known values. The fillArray() method accepts the admission numbers from the user. Although the question says the values are to be accepted in ascending order, the original solution also sorts the array after input. This makes the binary search step work even if the entered values are not perfectly ordered.
The sorting part compares every element with the elements after it. If an earlier element is greater than a later element, the two values are swapped. After these nested loops finish, the array is in ascending order. This is necessary because binary search depends on sorted data. Without sorting, comparing the search value with the middle element would not reliably tell us whether to move left or right.
The recursive method binSearch(int l, int u, int v) searches between the lower index l and upper index u. If the upper index becomes less than the lower index, the search range is empty, so the method returns -1. Otherwise, the middle index is calculated. If the middle element is equal to the value being searched, the method returns 1.
If the search value is greater than the middle element, it cannot be present in the left half because the array is sorted. Therefore the method calls itself for the right half. If the search value is smaller, it calls itself for the left half. Each recursive call reduces the search range, so the process moves towards either finding the value or reaching an empty range. The main() method uses the returned value to display whether the admission number was found.
Java Program:
/**
* The class Admission searches for an admission number
* using recursive binary search.
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
* @Question Year : ISC 2015 Theory Question 8
*/
import java.util.Scanner;
class Admission
{
int Adno[] = new int[100];
static Scanner sc = new Scanner(System.in);
Admission()
{
// Initialize all array elements to 0.
for(int i = 0; i < 100; i++)
{
Adno[i] = 0;
}
}
void fillArray()
{
for(int i = 0; i < 100; i++)
{
System.out.print("Enter Admission no of student " + (i + 1) + ": ");
Adno[i] = sc.nextInt();
}
// Sort the array in ascending order.
for(int i = 0; i < 99; i++)
{
for(int j = i + 1; j < 100; j++)
{
if(Adno[i] > Adno[j])
{
int temp = Adno[i];
Adno[i] = Adno[j];
Adno[j] = temp;
}
}
}
}
int binSearch(int l, int u, int v)
{
if(u < l)
{
return -1;
}
int mid = (l + u) / 2;
if(v == Adno[mid])
{
return 1;
}
else if(v > Adno[mid])
{
return binSearch(mid + 1, u, v);
}
else
{
return binSearch(l, mid - 1, v);
}
}
public static void main(String args[])
{
Admission ob = new Admission();
System.out.println("Enter Admission number in ascending order");
ob.fillArray();
System.out.print("Enter an Admission number to search : ");
int v = sc.nextInt();
int f = ob.binSearch(0, 99, v);
System.out.println("*****************************");
if(f == 1)
{
System.out.println("Admission Number found");
}
else
{
System.out.println("Admission Number Not found");
}
}
}Equivalent Python Program:
# Program to search an admission number using recursive binary search.
class Admission:
def __init__(self):
# Initialize the list with 100 zeroes.
self.adno = [0] * 100
def fill_array(self):
for i in range(100):
self.adno[i] = int(input("Enter Admission no of student " + str(i + 1) + ": "))
# Sort the admission numbers in ascending order.
self.adno.sort()
def bin_search(self, low, high, value):
if high < low:
return -1
mid = (low + high) // 2
if value == self.adno[mid]:
return 1
elif value > self.adno[mid]:
return self.bin_search(mid + 1, high, value)
else:
return self.bin_search(low, mid - 1, value)
ob = Admission()
print("Enter Admission number in ascending order")
ob.fill_array()
v = int(input("Enter an Admission number to search : "))
f = ob.bin_search(0, 99, v)
print("*****************************")
if f == 1:
print("Admission Number found")
else:
print("Admission Number Not found")Output:
Note: The sample output below shows 5 inputs for compact display. The actual program accepts 100 admission numbers.
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.