Part 2: binary search. When binary searching a sorted array that contains more than one key equal to the search key, the client may want to know the index of either the first or the last such key. Accordingly, implement the following API: public class BinarySearchDeluxe { // Returns the index of the first key in the sorted array a[] // that is equal to the search key, or -1 if no such key. public static int firstIndexof (Key[] a, Key key, Comparator comparator) // Returns the index of the last key in the sorted array af] // that is equal to the search key, or -1 if no such key. public static int lastIndexof (Key[] a, Key key, Comparator comparator) // unit testing (required) public static void main (String[ args) } Corner cases. Throw an 1llegalArgumentException if any argument to either firstIndexOf () or lastIndexof () is null. Preconditions. Assume that the argument array is in sorted order (with respect to the supplied comparator). Unit testing. Your main() method must call each public method directly and help verify that they work as prescribed (e.g., by printing results to standard output). Performance requirements. The firstIndexof () and lastIndexof ) methods must make at most 1+ [log, n] compares in the worst case, where n is the length of the array. In this context, a соmpare one call to comparator.compare ().
Part 2: binary search. When binary searching a sorted array that contains more than one key equal to the search key, the client may want to know the index of either the first or the last such key. Accordingly, implement the following API: public class BinarySearchDeluxe { // Returns the index of the first key in the sorted array a[] // that is equal to the search key, or -1 if no such key. public static int firstIndexof (Key[] a, Key key, Comparator comparator) // Returns the index of the last key in the sorted array af] // that is equal to the search key, or -1 if no such key. public static int lastIndexof (Key[] a, Key key, Comparator comparator) // unit testing (required) public static void main (String[ args) } Corner cases. Throw an 1llegalArgumentException if any argument to either firstIndexOf () or lastIndexof () is null. Preconditions. Assume that the argument array is in sorted order (with respect to the supplied comparator). Unit testing. Your main() method must call each public method directly and help verify that they work as prescribed (e.g., by printing results to standard output). Performance requirements. The firstIndexof () and lastIndexof ) methods must make at most 1+ [log, n] compares in the worst case, where n is the length of the array. In this context, a соmpare one call to comparator.compare ().
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
![Part 2: binary search. When binary searching a sorted array that contains more than one key equal to the search key, the client may want to know the index of either the first or the last such key.
Accordingly, implement the following API:
public class BinarySearchDeluxe {
// Returns the index of the first key in the sorted array a[]
// that is equal to the search key, or -1 if no such key.
public static <Key> int firstIndexof (Key[] a, Key key, Comparator<Key> comparator)
// Returns the index of the last key in the sorted array a[]
// that is equal to the search key, or -1 if no such key.
public static <Key> int lastIndexOf (Key[] a, Key key, Comparator<Key> comparator)
// unit testing (required)
public static void main (String [] args)
}
Corner cases. Throw an 1llegalArgumentException if any argument to either firstIndexOf() or lastIndexOf ( ) is null.
Preconditions. Assume that the argument array is in sorted order (with respect to the supplied comparator).
Unit testing. Your main () method must call each public method directly and help verify that they work as prescribed (e.g., by printing results to standard output).
Performance requirements. The firstIndexof () and lastIndexof () methods must make at most 1 + [log, n] compares in the worst case, where n is the length of the array. In this context, a
compare is one call to comparator.compare().](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa76acd85-1038-470b-93a5-cc8f3268b5fe%2F0b68ba1b-4f90-4540-a55e-20285f0d3e90%2F83pdop5_processed.png&w=3840&q=75)
Transcribed Image Text:Part 2: binary search. When binary searching a sorted array that contains more than one key equal to the search key, the client may want to know the index of either the first or the last such key.
Accordingly, implement the following API:
public class BinarySearchDeluxe {
// Returns the index of the first key in the sorted array a[]
// that is equal to the search key, or -1 if no such key.
public static <Key> int firstIndexof (Key[] a, Key key, Comparator<Key> comparator)
// Returns the index of the last key in the sorted array a[]
// that is equal to the search key, or -1 if no such key.
public static <Key> int lastIndexOf (Key[] a, Key key, Comparator<Key> comparator)
// unit testing (required)
public static void main (String [] args)
}
Corner cases. Throw an 1llegalArgumentException if any argument to either firstIndexOf() or lastIndexOf ( ) is null.
Preconditions. Assume that the argument array is in sorted order (with respect to the supplied comparator).
Unit testing. Your main () method must call each public method directly and help verify that they work as prescribed (e.g., by printing results to standard output).
Performance requirements. The firstIndexof () and lastIndexof () methods must make at most 1 + [log, n] compares in the worst case, where n is the length of the array. In this context, a
compare is one call to comparator.compare().
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education