/** A class for executing binary searches in an array. */ public class BinarySea
ID: 663181 • Letter: #
Question
/**
A class for executing binary searches in an array.
*/
public class BinarySearcher
{
/**
Finds a value in a range of a sorted array, using the binary
search algorithm.
@param a the array in which to search
@param low the low index of the range
@param high the high index of the range
@param value the value to find
@return the index at which the value occurs, or -1
if it does not occur in the array
*/
public static int search(int[] a, int low, int high, int value)
{
if (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] == value)
{
return mid;
}
else if (a[mid] < value )
{
return search(a, mid + 1, high, value);
}
else
{
return search(a, low, mid - 1, value);
}
}
else
{
return -1;
}
}
}
import java.util.Arrays;
import java.util.Scanner;
/**
This program demonstrates the binary search algorithm.
*/
public class BinarySearchDemo
{
public static void main(String[] args)
{
// Construct random array
int[] a = ArrayUtil.randomIntArray(20, 100);
Arrays.sort(a);
System.out.println(Arrays.toString(a));
Scanner in = new Scanner(System.in);
boolean done = false;
while (!done)
{
System.out.print
("Enter number to search for, -1 to quit: ");
int n = in.nextInt();
if (n == -1)
{
done = true;
}
else
{
int pos = BinarySearcher.search(a, 0, a.length - 1, n);
System.out.println("Found in position " + pos);
}
}
}
}
Explanation / Answer
/**
A class for executing binary searches in an array.
*/
public class BinarySearcher
{
/**
Finds a value in a range of a sorted array, using the binary
search algorithm.
@param a the array in which to search
@param low the low index of the range
@param high the high index of the range
@param value the value to find
@return the index at which the value occurs, or -1
if it does not occur in the array
*/
public static int search(int[] a, int low, int high, int value, int prevPos)
{
if (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] == value)
{
return mid+1;
}
else if (a[mid] < value )
{
return search(a, mid + 1, high, value, 0);
}
else
{
return search(a, low, mid - 1, value, -1*(mid+1));
}
}
else
{
return prevPos;
}
}
}
import java.util.Arrays;
import java.util.Scanner;
/**
This program demonstrates the binary search algorithm.
*/
public class BinarySearchDemo
{
public static void main(String[] args)
{
// Construct random array
int[] a = ArrayUtil.randomIntArray(20, 100);
Arrays.sort(a);
System.out.println(Arrays.toString(a));
Scanner in = new Scanner(System.in);
boolean done = false;
while (!done)
{
System.out.print
("Enter number to search for, -1 to quit: ");
int n = in.nextInt();
if (n == -1)
{
done = true;
}
else
{
int pos = BinarySearcher.search(a, 0, a.length - 1, n, -1);
if(pos == 0)
System.out.println("Not Found , but comes at last of the array");
else if(pos < 0)
System.out.println("Not Found, but it should be inserted before position: " + (pos*-1));
else
System.out.println("Found in position " + pos);
}
}
}
}
------------------------------------------------------------
OUTPUT
----------------------------------------------------------------
[11, 12, 13, 15, 16, 17]
Enter number to search for, -1 to quit: 10
Not Found, but it should be inserted before position: 1
Enter number to search for, -1 to quit: 30
Not Found , but comes at last of the array
Enter number to search for, -1 to quit: 14
Not Found, but it should be inserted before position: 4
Enter number to search for, -1 to quit: 11
Found in position 1
Enter number to search for, -1 to quit: -1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.