Page 125 - Computer science 868 Class 12
P. 125
2. State the best case and the worst case complexity for bubble sort algorithm. [ISC 2023]
Ans. O(n): Best case complexity for bubble sort algorithm.
2
O(n ): Worst case complexity for bubble sort algorithm
3. Design a class BinSearch to search for a particular value in an array. Some of the members of the class are given below: [ISC 2020]
Classname : 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 ) : parameterised 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.
Ans. import java.util.*;
class BinSearch
{
int arr[];
int n;
static Scanner x=new Scanner(System.in);
BinSearch(int nn)
{
n=nn;
}
void fillarray()
{
arr=new int[n];
System.out.println(“Enter “+n + “ elements”);
for(int i =0;i<n;i++)
arr[i]=x.nextInt();
}
void sort()
{
int t;
for(int i=0;i<n-1;i++)
for(int j =0;j<n-1-i;j++)
{
if (arr[j]>arr[j+1])
{
t=arr[j];
arr[j]=arr[j+1];
arr[j+1]=t;
}
}
}
int bin_search(int l,int u, int v )
{
int m=(l+u)/2;
if(arr[m]==v)
return m;
else if(l>u)
return -1;
else if (arr[m]>v)
123
Implementation of Algorithms to Solve Problems 123

