Implement a function that uses binary search to find the index position of a giv
ID: 643441 • Letter: I
Question
Implement a function that uses binary search to find the index position of a given value k in an array of integers whose eements are in strictly increasing order. searches for a given value k in an array of integers. If the value is found, the function returns the index of the value in the array; otherwise it returns -1. For example, for v = (-2, 4, 5, 6, 8) and k = 1, the function returns -1. and for k = 4 it returns 1. A declaration of the function is given above. Include test code with assertions.
Explanation / Answer
Program plan:
In this program we need to take an array of elements and those elements must be in ascending order.Hence, the following methods should be defined.
void ascending(int a[],int size):this method is used to sort the array elements in ascending order.a[] is the array and size describes the size of the array.so the user need not enter elemnets in ascending order.this method sorts it.
int binarySearch(int a[],int size,int k): This method is used to find the index of the given value.this method returns -1 if the value is not in the array.if the value found ,it returns position of the value in array.since array index starts from 0 so we need add 1 to print the exact value in the list of numbers.
these two methos are defined in "BinarySearch" class. the main method is BinaryClass.
Program code:
/*import directives declaration.In this program we Scanner class to read the input from keyboard.Scanner class is defined in java.util package.it requires input device object System.in as argument*/
import java.lang.*;
import java.util.*;
//main class
class BinaryClass
{
//main method
public static void main(String args[])
{
Scanner s=new Scanner(System.in); //Scanner class object instantiation
BinarySearch bs=new BinarySearch(); //BinarySearch class object instantiation
int a[],n,k,index;
System.out.println("enter array size:");
n=s.nextInt();
a=new int[n]; //initializes array with the required size
System.out.println("enter elements for array in increasing order: ");
for(int i=0;i<n;++i)a[i]=s.nextInt();
System.out.println("enter the search element: ");
k=s.nextInt();
bs.ascending(a,k); //calling the ascending method using BinarySearch class object
index=bs.binarySearch(a,n,k);
if(index==-1) System.out.println("Element not found");
else System.out.println("element found in "+(index+1)+ " place");
} // end of main()
}// end of class BinaryClass
class BinarySearch
{
int first,last,mid,a[];
int binarySearch(int a[],int size,int k)
{
first=0;
last=size;
while(first<=last)
{
mid=(first+last)/2;
if(a[mid]==k) return mid;
else if(a[mid]<k) first=mid+1;
else if(a[mid]>k)last=mid-1;
}
return -1;
} // end of binarySearch method
void ascending(int a[],int size)
{
int temp;
for(int i=0;i<size;++i)
{
for(int j=i+1;j<size;++j)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
System.out.println("array elements in ascending order is:");
for(int i=0;i<size;++i)System.out.println(a[i]);
}// end of ascending method
}//end of BinarySearch class
Sample output:
enter array size:
5
enter elements for array in increasing order:
2
6
5
3
4
enter the search element:
5
array elements inascending order is:
2
3
4
5
6
element found in 4 place
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.