Develop a program to perform a binary search on a one-dimensional integer array
ID: 3698228 • Letter: D
Question
Develop a program to perform a binary search on a one-dimensional integer array LIST of dimension N. You should develop an independent search method (call itBinSearch), and write your program so that the BinSearch method is invoked from your main program or another method. The BinSearch method should accept a search key parameter and return a Boolean value (Success). Maintain a count of the number of comparisons attempted during the execution of the method. Assume the array is already sorted in ascending order, and that there are no duplicate entries. Use a while loop for the binary search.
Repeat the above assignment using a recursive method for the binary search instead of the while loop.
Repeat the above to perform a sequential search on the same array.
In each of the above cases, maintain a count of the number of iterations needed to perform the different search functions on the same array.
I all cases, remember to include the condition when a search key is NOT found in the array.
Explanation / Answer
import java.util.Scanner;
class BinaryKey
{
public static void main(String args[])
{
int c, first, last, middle, n, search, array[];
//reading array elements by asking user
Scanner in = new Scanner(System.in);
System.out.println("Enter number of elements");
n = in.nextInt();
array = new int[n];
System.out.println("Enter " + n + " integers");
for (c = 0; c < n; c++)
array[c] = in.nextInt();
System.out.println("Enter value to find");
k= in.nextInt();
BinaryKey bk=new BinaryKey();
bk. itBinSearch(k);
public boolean itBinSearch(int key)
{
first = 0;
last = n - 1;
middle = (first + last)/2;
while( first <= last )
{
if ( array[middle] < key)
first = middle + 1;
else if ( array[middle] == key)
{
System.out.println(key+ " found at location " + (middle + 1) + ".");
return true;
}
else
{
last = middle - 1;
middle = (first + last)/2;
}
}//while
if ( first > last )
System.out.println(key+ " is not present in the list. ");
return false;
}//function
}//main
}//class
//for recursive search
public boolean itBinSearch(int key)
{
if (first < last)
{
int mid = first + (last - first) / 2;
if (key < array[mid])
{
return itBinSearch(array, first, mid, key);
}
else if (key > array[mid])
{
return itBinSearch(array, mid+1, last , key);
}
else
{
return mid;
}
}
return false;
}
//using sequailtnal search
public boolean itBinSearch(int key)
{
for (int c = 0; c< last; c++)
{
if (array[c] == key)
{
System.out.println(key+ " is present at location " + (c + 1) + ".");
return true;
}
}
if (c ==last)
System.out.println(key + " is not present in array.");
return false;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.