‹ Back to the paper
Question 8
10 marks
Computer ScienceISC 2020 Computer Science Paper 1ProgramObjects
Write the program described below.
Design a class BinSearch to search for a particular value in an array. Some of the members of the…
Design a class BinSearch to search for a particular value in an array. Some of the members of the class are given below:
Class name : BinSearch
Data members/instance variables:
arr[ ] : to store integer elements
n : integer to store the size of the array
Member functions/methods:
BinSearch(int nn) : parameterized constructor to initialize n=nn
void fillarray( ) : to enter elements in the array
void sort( ) : sorts the array elements in ascending order using any standard sorting technique
int bin_search(int l, int u, int v) : searches for the value ‘v’ using binary search and recursive technique and returns its location if found otherwise returns -1
Define the class BinSearch giving details of the constructor( ), void fillarray( ), void sort( ) and int bin_search(int, int, int). Define the main( ) function to create an object and call the functions accordingly to enable the task.
Answer
Answer
import java.util.Scanner;
class BinSearch
{
int arr[];
int n;
BinSearch(int nn)
{
n = nn;
arr = new int[n];
}
void fillarray()
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter " + n + " elements:");
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt();
}
void sort()
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
}
int bin_search(int l, int u, int v)
{
if (l > u)
return -1;
int mid = (l + u) / 2;
if (arr[mid] == v)
return mid;
else if (v < arr[mid])
return bin_search(l, mid - 1, v);
else
return bin_search(mid + 1, u, v);
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
int size = sc.nextInt();
BinSearch ob = new BinSearch(size);
ob.fillarray();
ob.sort();
System.out.print("Sorted array: ");
for (int i = 0; i < size; i++)
System.out.print(ob.arr[i] + " ");
System.out.println();
System.out.print("Enter the value to search: ");
int v = sc.nextInt();
int pos = ob.bin_search(0, size - 1, v);
if (pos == -1)
System.out.println(v + " not found");
else
System.out.println(v + " found at index " + pos);
}
}Explanation: The constructor stores the size and creates the array. fillarray() reads the elements. sort() arranges them in ascending order using bubble sort (binary search needs a sorted array). bin_search(l, u, v) is recursive: if l > u the value is absent and -1 is returned; otherwise it compares v with the middle element and returns mid if equal, else searches the left half (l to mid-1) or the right half (mid+1 to u). Tested: for the array 45 12 89 7 33 60 the sorted array is 7 12 33 45 60 89 and searching 33 gives index 2.