Although keys in a map are distinct, the binary search algorithm can be applied in a more
Question:
Transcribed Image Text:
public class Sorted TableMap
public class Sorted TableMap extends AbstractSortedMap { private ArrayList> table public Sorted TableMap() { super(); } public Sorted TableMap(Comparator comp) { super(comp); } /** Returns the smallest index for range table[low.high] inclusive storing an entry with a key greater than or equal to k (or else index high+1, by convention). */ private int findIndex(K key, int low, int high) { if (high < low) return high + 1; int mid = (low + high) / 2; int comp = compare(key, table.get(mid)); if (comp == 0) return mid; else if (comp < 0) return findlndex(key, low, mid – 1); // answer is left of mid (or possibly mid) else new ArrayList<>((); // no entry qualifies 10 11 // found exact match 12 13 14 15 return findlndex(key, mid + 1, high); // answer is right of mid } /** Version of findIndex that searches the entire table */ private int findlndex(K key) { return findIndex(key, 0, table.size() – 1); } /** Returns the number of entries in the map. */ public int size() { return table.size(); } /** Returns the value associated with the specified key (or else null). */ public V get(K key) { int j = findlndex(key); if (j == size() || compare(key, table.get(j)) != 0) return null; // no match return table.get(j).getValue( ); 16 17 18 19 20 21 22 23 24 25 26 27 /** Associates the given value with the given key, returning any overridden value.*/ public V put(K key, V value) { int j = findlndex(key); if (j < size() && compare(key, table.get(j)) == 0) return table.get(j).setValue(value); table.add(j, new MapEntry(key, value)); return null; } /** Removes the entry having key k (if any) and returns its associated value. */ public V remove(K key) { int j = findlndex(key); if (j == size() || compare(key, table.get(j)) != 0) return null; // no match return table.remove(j).getValue(); } 28 29 30 // match exists 31 32 // otherwise new 33 34 35 36 37 38 39 40 41
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 62% (16 reviews)
The original version of Code Fragment 1011 does not guarantee that it finds the leftmost occ...View the full answer
Answered By
Branice Buyengo Ajevi
I have been teaching for the last 5 years which has strengthened my interaction with students of different level.
4.30+
1+ Reviews
10+ Question Solved
Related Book For
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Question Posted:
Students also viewed these Computer science questions
-
Write a program that animates the binary search algorithm. Create an array with numbers from 1 to 20 in this order. The array elements are displayed in a histogram, as shown in Figure 22.13. You need...
-
Recall that Chapter 8 described the binary search algorithm for finding a particular entry in an ordered list. The idea behind binary search is to begin looking in the exact center of the list. If...
-
During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. Such a set is called persistent. One way to implement a persistent set...
-
The administrator of Hope Hospital has been asked to perform an activity analysis of the emergency room (ER). The ER activities include cost of quality and other patient care activities. The lab...
-
Altira Corporation uses a periodic inventory system. The following information related to its merchandise inventory during the month of August 2018 is available: Aug. 1 Inventory on hand-2,000 units;...
-
A medical researcher wishes to determine if the way people pay for their medical prescriptions is distributed as follows: 60% personal funds, 25% insurance, 15% Medicare. A sample of 50 people found...
-
What is the purpose of an API and an SDK? Provide an example of how a business might make use of an API or SDK.
-
The following is a list of defalcations that have occurred within various organizations. You may assume that the amounts involved are material. Required For each defalcation, briefly indicate: a. How...
-
While scrolling through your favorite social media site, apicture of Philodendron ?a common houseplant?catchesyour eye. Your friend says about the photo, ?This houseplant and Iare best friends. It?s...
-
Suppose three competing airlines each schedule their own flight to Waco which arrives there between 2:00 and 3:00 pm according to a continuous uniform distribution. All three flights are mutually...
-
Suppose we are given two sorted search tables S and T, each with n entries (with S and T being implemented with arrays). Describe an O(log 2 n)-time algorithm for finding the k th smallest key in the...
-
Describe how to perform a removal from a hash table that uses linear probing to resolve collisions where we do not use a special marker to represent deleted elements. That is, we must rearrange the...
-
For each of the following compounds, give the systematic name and the common name (for those that have common names), and indicate whether the amines are primary, secondary, or tertiary: a. b. c....
-
Hampton Company reports the following information for its recent calendar year. Income Statement Data Sales Expenses: Cost of goods sold Salaries expense Depreciation expense Net income Required: $...
-
Write a program to find properties of a group of numbers. Please Enter the total number of group's member please enter 1. number: 12 please enter 2. number: 56 please enter 3. number: -90 : 6 please...
-
(e) This is the network structure of a set of websites: B A C E D MyRank is a simplified PageRank algorithm, where each page begins with a value of 1, and at each round a page shares 0.8 times its...
-
Consider the following program: program main var X: int; int function funl (test: bool) procedure fun 3 // begin of fun3 begin print x;
-
FlightID DepartureAirport TargetAirport [CustomerName, DateOfDeparture CustomerMemberNr] XC587,PA897 LHR LAX John Taylor, 2231 10/4/2022 26/5/2022 TC487 IST LHR Mustafa Ahmed, 14/5/2022 7723 NX223...
-
Given a specific sample to estimate a specific parameter from a population, what are the expected similarities and differences in the corresponding sampling distribution (using the given sample size)...
-
Is times interest earned meaningful for utilities? Why or why not?
-
Why don't we need to set or reset the prev attributes of objects in the implementation of the ALLOCATE-OBJECT and FREE-OBJECT procedures?
-
Write an O(n)-time non recursive procedure that, given an n-node binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure.
-
As written, each loop iteration in the LIST-SEARCH procedure requires two tests: one for x L.nil and one for x.key k. Show how to eliminate the test for x L.nil in each iteration.
-
Shakespearenever fails to stun an audience with a complex yet entertaining character. HisplayofMacbethis no exception. One might judge Macbeth to be the valiant hero of the play, to the audiences...
-
In the context of performance management in not-for-profit organizations, Discuss the difference between objectives, Outputs, outcomes, and impact. Give an example of an objective, an output, And an...
-
Evidence is used to make a decision whenever the decision follows directly from the evidence (Tingling & Brydon, 2010). This is where so many people get it wrong or going by their personal beliefs or...
Study smarter with the SolutionInn App