1 answer

1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array...

Question:

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" array is either a sorted array, or it consists of two sorted subarrays, such that every element of the first subarray is greater or equal than every element of the second subarray.

For example, the array {3, 17, 28, 935, 1011, -10, 0, 2} is "almost sorted" since it consists of two sorted subarrays: {3, 17, 28, 935, 1011} and {-10, 0, 2} with the property that each element in the first subarray is greater or equal than every element of the second subarray.

Note: One of the subarrays can be empty, i.e., the array might be sorted.

You need to develop an efficient modification of the Binary Search Algorithm, with worst-case running time of ( ) for an array of n elements.

Reminder: In Java, elements of an array of n elements have indexes 0…n-1.

Formally speaking, your input is an array of distinct integers, and the element x to find; your output is: the index of x in the array, or -1 in case x is not there.

With the array above and x=935, the algorithm has to return 3 (the index of the element 935 in the array).

Please develop the following Java function:

public static int FindIndex(int[] arr, int x)

Here arr is the array of distinct integers, x is the element to find.

NOTE: In your algorithm, you do not have to check that the array is "almost sorted". However, you have to check "boundary cases" like an empty array.


Answers


import java.util.*;
public class Main
{
static int 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 mid;
  
// If element is smaller than mid, then it can only
// be present in left subarray
if (arr[mid] > x)
{ int rr= binarySearch(arr, l, mid - 1, x);
if(rr==-1)//modified
{
return binarySearch(arr, mid + 1, r, x);
}
return rr;
}
// Else the element can only be present in right
// subarray
int k =binarySearch(arr, mid + 1, r, x);
//modified part
if(k==-1)
{
return binarySearch(arr, l, mid - 1, x);
}
return k;
}
  
// We reach here when element is not present in array
return -1;
}
  
public static int FindIndex(int[] arr, int x)
{
if(arr.length==0)return -1;//if array is empty
return binarySearch(arr,0,arr.length-1,x);
  
}
   public static void main(String[] args) {
   int a[] = {3, 17, 28, 935, 1011, -10, 0, 2} ;//declaring array
   int r = FindIndex(a,935);
       System.out.println("index of 935:"+r);
       r = FindIndex(a,-10);
       System.out.println("index of -10:"+r);
      
       r = FindIndex(a,0);
       System.out.println("index of 0:"+r);
      
       r = FindIndex(a,1);
       System.out.println("index of 1:"+r);
      
       r = FindIndex(a,3);
       System.out.println("index of 3:"+r);
      
       r = FindIndex(a,2);
       System.out.println("index of 2:"+r);
      
       r = FindIndex(a,17);
       System.out.println("index of 17:"+r);
   }
}

output:

index of 935:3                                                                                                                                                                   

index of -10:5                                                                                                                                                                   

index of 0:6                                                                                                                                                                     

index of 1:-1                                                                                                                                                                    

index of 3:0                                                                                                                                                                     

index of 2:7                                                                                                                                                                     

index of 17:1                                                                                                                                                                    

      


//PLS give a thumbs up if you find this helpful, it helps me alot, thanks.


//if you have any doubts, ask me in the comments

  

.

Similar Solved Questions

1 answer
Suppose the market demand for cigarettes is given in the following table. Suppose further that smoking...
Suppose the market demand for cigarettes is given in the following table. Suppose further that smoking creates external costs valued at $0.50 per pack. Graph the social and market demand curves and answer two questions about the market and socially optimal quantities. Quantity Price (5 per pack) (pa...
1 answer
Chech Presented here are the comparative balance sheets of Hames Inc. at December 31, 2020 and...
Chech Presented here are the comparative balance sheets of Hames Inc. at December 31, 2020 and 2019. Sales for the year ended December 31, 2020, totaled $670,000. HAMES INC. Balance Sheets December 31, 2020 and 2019 2020 2019 $ 25,000 78,000 103,000 $ 206,000 50,000 125,000 (65,000) $ 316,000 $ 20,0...
1 answer
Return on Investment The income from operations and the amount of invested assets in each division...
Return on Investment The income from operations and the amount of invested assets in each division of Beck Industries are as follows: Income from Operations Invested Assets Retail Division $81,900 $390,000 Commercial Division 86,400 480,000 Internet Division 124,800 780,000 a. Compute the return on ...
1 answer
Calculate the pH of the solution that results from each of the following mixtures. 1. 50.0...
Calculate the pH of the solution that results from each of the following mixtures. 1. 50.0 mL of 0.15 molL−1 HCOOH (Ka=1.8×10−4) with 80.0 mL of 0.13 molL−1 HCOONa 2. 125.0 mL of 0.11 molL−1 NH3 (Kb=1.76×10−5) with 240.0 mL of 0.11 molL−1 NH4Cl Express...
1 answer
Barbituric acid (1) is the backbone for common central nervous system depressants with anesthetic anxiolytic, and...
Barbituric acid (1) is the backbone for common central nervous system depressants with anesthetic anxiolytic, and hypnotic properties. If the active allosteric pharmacophore is present as HA. calculate the a) pH and b) percentage of 2 in 10-M barbituric acid....
1 answer
DIAZ ENTERTAINMENT Cash Account Records May 1, 2021, to May 31, 2021 Cash Balance May 31,...
DIAZ ENTERTAINMENT Cash Account Records May 1, 2021, to May 31, 2021 Cash Balance May 31, 2021 $5,200 Cash Balance Cash May 1, 2021 + Receipts $5,330 $11,790 Cash Receipts Date Desc. 5/3 Sales 5/10 Sales 5/17 Sales 5/24 Sales 5/31 Sales Amount $ 1,410 1,840 2,470 2,940 3,130 Date 5/7 5/12 5/15 5/22 ...
1 answer
The relative molecular weight of acetic acid is 60.05 and its density is 1.049g/ml. Describe how you would prepare 1L of 2M solution of acetic acid?
The relative molecular weight of acetic acid is 60.05 and its density is 1.049g/ml. Describe how you would prepare 1L of 2M solution of acetic acid?...
1 answer
In a closed Hydraulic system, a load is placed on a 4 inch diameter small piston...
In a closed Hydraulic system, a load is placed on a 4 inch diameter small piston and creates 10 psi of pressure. The larger piston is 15 square inches. How much force is created on the small piston? Load Hydraulic Pressure...
1 answer
QUESTION 4 You are given two loans, with each loan to be repaid by a single payment in the future. Each payment include...
QUESTION 4 You are given two loans, with each loan to be repaid by a single payment in the future. Each payment includes both principal and interest. The first loan is repaid by a 3000 payment at the end of four years. The interest is accrued at an annual nominal rate of discount equal to 5% compoun...
1 answer
St r ade OOK ORION Downloadable eTextbook ent CALCULATOR FULL SCREEN PRINTER VERSION BACK NET Brief Exercise 6-9 At...
st r ade OOK ORION Downloadable eTextbook ent CALCULATOR FULL SCREEN PRINTER VERSION BACK NET Brief Exercise 6-9 At December 31, 2015, the following information was available for A. Kamble Company: ending Inventory $42,510, beginning inventory $57,430, cost of goods sold $260,330, and sales revenue ...
1 answer
Required information Use the following information for the Exercises below. [The following information applies to the...
Required information Use the following information for the Exercises below. [The following information applies to the questions displayed below.) Laker Company reported the following January purchases and sales data for its only product. Units sold at Retail Units Acquired at Cost 215 units @ $14.00...
1 answer
A function that prints the binary search tree’s all nodes level by level, output statement 50,...
a function that prints the binary search tree’s all nodes level by level, output statement 50, 30, 70, 20, 40, 60, 80 50 / \ 30 70 / \ / \ 20 40 60 80      ...
1 answer
H) The healch of Orthodos Jews in Bedford, Stxyvesant の78 o Which type ome of seudy...
h) The healch of Orthodos Jews in Bedford, Stxyvesant の78 o Which type ome of seudy in nedical rescarch establäshes a cause and effect relationship? b) Epidemiological studies e) Surveys d) Clinical or experimental 1 Which type ee of form arh sty s interviews,surveys and measurements of ...
1 answer
Once monthly posting has been completed, the account receivable (A/R) subsidiary ledger should be: a. subtracted...
Once monthly posting has been completed, the account receivable (A/R) subsidiary ledger should be: a. subtracted b. amortized c. journalized, posted, and printed. d. totaled...
1 answer
A publication entitled, "Health-related quality of life among patients with cervical cancer" most likely represents results...
A publication entitled, "Health-related quality of life among patients with cervical cancer" most likely represents results of: a. Research b. Quality improvement c. Evidenced base practice...
1 answer
Please explain how problems solved with Excel steps shown/displayed. 2. SHELFISH 1: As the finance manager...
Please explain how problems solved with Excel steps shown/displayed. 2. SHELFISH 1: As the finance manager of Shelfish Incorporated, you are considering purchasing a new piece of equipment for which the company estimates: • Equipment Cost $290,000 with useful life of 7 years; straight line depr...
1 answer
3. CIN: A 50 m long section of a steam pipe at 15°C. The average temperature...
3. CIN: A 50 m long section of a steam pipe at 15°C. The average temperature of the outer surface of combined heat transfer coefficient or the rate of heat loss from the steam plp generated in an natural gas furnance $0.52/therm (1 therm = 105, 0.035 W/mK) needed in order to say remain constant ...