Prashnikaप्रश्निका
Code
About
‹ 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.