Create a program that uses a recursive function to check whether a number is in
ID: 3590205 • Letter: C
Question
Create a program that uses a recursive function to check whether a number is in a list of
Sorted numbers.
In order to understand recursion read your note from pre-requisite course (district math)
Specifications
The program should begin by generating list of 10 random numbers from 1 to 100.
The program should allow the user to enter a number from 1 to 100. Then, it should display whether that number is or isn’t in the list of random numbers.
Use binary search algorithm to search the list of random numbers
Sample console output
Binary Search
Enter 'x' to exit
Random numbers: [13, 16, 18, 29, 32, 71, 71, 77, 78, 90]
Enter a number from 1 to 100: 1
1 is NOT in random numbers.
Enter a number from 1 to 100: 32
32 is in random numbers.
Enter a number from 1 to 100: 100
100 is NOT in random numbers.
Design: Draw an UML class diagram for the class and coding
Explanation / Answer
Hi friend, You have not mentioned about Programming language.
I have implementated in Java.
You can take help from my code.
import java.util.Random;
import java.util.Scanner;
//Java implementation of recursive Binary Search
public class BinarySearch
{
// Returns index of x if it is present in arr[l..r], else
// return -1
public static boolean binarySearch(int arr[], int l, int r, int x)
{
if (r>=l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle itself
if (arr[mid] == x)
return true;
// If element is smaller than mid, then it can only
// be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present in right
// subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present in array
return false;
}
// Driver method to test above
public static void main(String args[])
{
int n = 10;
int arr[] = new int[n];
Random random = new Random();
for(int i=0; i<n; i++)
arr[i] = random.nextInt(100)+1;
Scanner sc = new Scanner(System.in);
int key;
System.out.println("Enter '-1' to exit");
while(true) {
System.out.print("Enter a number from 1 to 100: ");
key = sc.nextInt();
if(key == -1)
break;
boolean result = binarySearch(arr,0,n-1,key);
if (result)
System.out.println(key+" is in random numbers.");
else
System.out.println(key+" is NOT in random numbers.");
}
sc.close();
}
}
/*
Sample run:
Enter '-1' to exit
Enter a number from 1 to 100: 1
1 is NOT in random numbers.
Enter a number from 1 to 100: 32
32 is NOT in random numbers.
Enter a number from 1 to 100: 56
56 is NOT in random numbers.
Enter a number from 1 to 100: -1
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.