In Java: In a sorted (ascending) integer array of length n with no duplicates, print all values in the range x to y. Assume both x and y are in the array. What is the worst case big O running time if there are k integers within the range?
Answer:
Explanation:
The worst case should be O(n) as we need to traverse the whole array.
Code:
public class Main
{
public static void main(String[] args) {
int a[] = {2, 3, 4, 7, 9, 10,
17};
int x = 4, y=10;
for(int i=0; i<a.length;
i++)
{
if(a[i]>=x &&
a[i]<=y)
System.out.print(a[i]+" ");
}
}
}
Output:
PLEASE UPVOTE IF YOU FOUND THIS HELPFUL!
In Java: In a sorted (ascending) integer array of length n with no duplicates, print all...
The input is an array of N integers ( sorted ) and an integer X. The algorithm returns true if X is in the array and false if X is not in the array. Describe an algorithm that solves the problem with a worst case of O(log N) time.
Given two arrays A and B of n integers both of which are sorted in ascending order. Write an algorithm to check whether or not A and B have an element in common. Find the worst case number of array element comparisons done by this algorithm as a function of n and its Big-O complexity
1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array of distinct integers, and an integer x, return the index of x in the array. If the element x is not present in the array, return -1. "Almost sorted" means the following. Assume you had a sorted array A[0…N], and then split it into two pieces A[0…M] and A[M+1…N], and move the second piece upfront to get the following: A[M+1]…A[N]A[0]…A[M]. Thus, the "almost sorted"...
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a method to perform a binary search for a target value in nums. If target exists, then return its index, otherwise return -1. Analyze the running time, T(n). public int search(int[] nums, int target) { // YOUR CODE GOES HERE } // end search
Implement a method to build an AVL tree out of a sorted (ascending order) array of unique integers, with the fastest possible big O running time. You may implement private helper methods as necessary. If your code builds a tree that is other than an AVL tree, you will not get any credit. If your code builds an AVL tree, but is not the fastest big O implementation, you will get at most 12 points. You may use any of...
We are given an array A holding n integers, for some large n. The array is sorted, and the values in A range from -2147483648 to 2147483647, evenly distributed. Give Θ expressions for the following tasks: A. Running the insertion sort algorithm on the array A: B. Running the selection sort algorithm on the array A: C. Performing binary search for integer k which is not in A: D. Performing interpolation search for integer k not in A:
by netBeans C++ java by netBeans C++ java by netBeans C++ java 1. Answer the following question a) (4 marks) Write a Java method, which takes an integer array and two integers x and y as input parameters. The method should exchange the value in position x with the value in the position y in the array. Example: If x = 1, y=2 Input Array Output Array b) (4 marks) Write the main method to do the following: 1. Define...
Refer to the following program sample to answer the parts (a-i) below. Keep in mind that low and high are both indices of array A. /1 Assume that A is a sorted array containing N integers // Assume that x is a variable of type int int low= 0; // Line 1 int high- N; // Line 2 while (low- high) I/ Line 3 m- (lowthigh)/2; // Line 4 (This is integer division) if (A [m]<) I/Line 5 then low-...
write a java program Accept a positive integer n from keyboard and then create an array or arraylist containing n random elements within the range [-n,n). Print out the random array or arraylist, and then find out and print out the number of inversions and the maximum subarray (index range of the maximum subarray along with the maximum subarray sum) in the array or arraylist using divide and conquer, respectively. For example, suppose we accept integer 6 from keyboard, then...
1. Design and write a Divide& Conquer algorithm that, given an array A of n distinct integers which is already sorted into ascending order, will find if there is some i such that Ali] in worst-case 0(log n) time.