1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Roman55 [17]
2 years ago
12

Let's implement a classic algorithm: binary search on an array. Implement a class named BinarySearcher that provides one static

method named search. search takes a SearchList as its first parameter and a Comparable as its second. If either parameter is null, or if the SearchList is empty, you should throw an IllegalArgumentException. SearchList is a provided class. It provides a get(int) method that returns the Comparable at that index, and a size method that returns the size of the SearchList. Those are the only two methods you should need! search returns a boolean indicating whether the passed value is located in the sorted SearchList. To search the sorted SearchList efficiently, implement the following algorithm: Examine the value in the middle of the current array (index (start + end) / 2) If the midpoint value is the value that we are looking for, return true If the value that we are looking for is greater than the midpoint value, adjust the current array to start at the midpoint if the value that we are looking for is less than the midpoint value, adjust the current array to end at the midpoint Continue until you find the value, or until the start reaches the end, at which point you can give up and return false This is a fun problem! Good luck! Keep in mind that every time you call SearchList.get that counts as one access, so you'll need to reduce unnecessary accesses to pass the test suite.
Computers and Technology
1 answer:
yKpoI14uk [10]2 years ago
7 0

Answer:

Hope this helped you, and if it did , do consider giving brainliest.

Explanation:

import java.util.ArrayList;

import java.util.List;

//classs named BinarySearcher

public class BinarySearcher {

 

//   main method

  public static void main(String[] args) {

     

//   create a list of Comparable type

     

      List<Comparable> list = new ArrayList<>();

     

//       add elements

     

      list.add(1);

      list.add(2);

      list.add(3);

      list.add(4);

      list.add(5);

      list.add(6);

      list.add(7);

     

//       print list

     

      System.out.println("\nList : "+list);

     

//       test search method

     

      Comparable a = 7;

      System.out.println("\nSearch for 7 : "+search(list,a));

     

      Comparable b = 3;

      System.out.println("\nSearch for 3 : "+search(list,b));

     

      Comparable c = 9;

      System.out.println("\nSearch for 9 : "+search(list,c));

     

      Comparable d = 1;

      System.out.println("\nSearch for 1 : "+search(list,d));

     

      Comparable e = 12;

      System.out.println("\nSearch for 12 : "+search(list,e));

     

      Comparable f = 0;

      System.out.println("\nSearch for 0 : "+search(list,f));

     

  }

 

 

 

//   static method named search takes arguments Comparable list and Comparable parameter

  public static boolean search(List<Comparable> list, Comparable par) {

     

//       if list is empty or parameter is null the throw IllegalArgumentException

     

      if(list.isEmpty() || par == null ) {

         

          throw new IllegalArgumentException();

         

      }

     

//       binary search

     

//       declare variables

     

      int start=0;

     

      int end =list.size()-1;

     

//       using while loop

     

      while(start<=end) {

         

//           mid element

         

          int mid =(start+end)/2;

         

//           if par equal to mid element then return

         

          if(list.get(mid).equals(par) )

          {

              return true ;

             

          }  

         

//           if mid is less than parameter

         

          else if (list.get(mid).compareTo(par) < 0 ) {

                 

              start=mid+1;

          }

         

//           if mid is greater than parameter

         

          else {

              end=mid-1;

          }

      }

     

//       if not found then retuen false

     

      return false;

     

  }

 

 

}import java.util.ArrayList;

import java.util.List;

//classs named BinarySearcher

public class BinarySearcher {

 

//   main method

  public static void main(String[] args) {

     

//   create a list of Comparable type

     

      List<Comparable> list = new ArrayList<>();

     

//       add elements

     

      list.add(1);

      list.add(2);

      list.add(3);

      list.add(4);

      list.add(5);

      list.add(6);

      list.add(7);

     

//       print list

     

      System.out.println("\nList : "+list);

     

//       test search method

     

      Comparable a = 7;

      System.out.println("\nSearch for 7 : "+search(list,a));

     

      Comparable b = 3;

      System.out.println("\nSearch for 3 : "+search(list,b));

     

      Comparable c = 9;

      System.out.println("\nSearch for 9 : "+search(list,c));

     

      Comparable d = 1;

      System.out.println("\nSearch for 1 : "+search(list,d));

     

      Comparable e = 12;

      System.out.println("\nSearch for 12 : "+search(list,e));

     

      Comparable f = 0;

      System.out.println("\nSearch for 0 : "+search(list,f));

     

  }

 

 

 

//   static method named search takes arguments Comparable list and Comparable parameter

  public static boolean search(List<Comparable> list, Comparable par) {

     

//       if list is empty or parameter is null the throw IllegalArgumentException

     

      if(list.isEmpty() || par == null ) {

         

          throw new IllegalArgumentException();

         

      }

     

//       binary search

     

//       declare variables

     

      int start=0;

     

      int end =list.size()-1;

     

//       using while loop

     

      while(start<=end) {

         

//           mid element

         

          int mid =(start+end)/2;

         

//           if par equal to mid element then return

         

          if(list.get(mid).equals(par) )

          {

              return true ;

             

          }  

         

//           if mid is less than parameter

         

          else if (list.get(mid).compareTo(par) < 0 ) {

                 

              start=mid+1;

          }

         

//           if mid is greater than parameter

         

          else {

              end=mid-1;

          }

      }

     

//       if not found then retuen false

     

      return false;

     

  }

 

 

}

You might be interested in
The ArrayList class contains a trim method that resizes the internal array to exactly the capacity. The trim method is intended
andreev551 [17]

Answer:

public void trimToSize() {

modCount++;

if (size < elementData.length) {

elementData = (size == 0)

? EMPTY_ELEMENTDATA

: Arrays.copyOf(elementData, size);

}

}

Now, the running time for copyOf() function is O(N) where N is the size/capacity of the ArrayList. Hence, the time complexity of trimToSize() function is O(N).

Hence, the running time of building an N-item ArrayList is O(N^2).

Please find the sample code below.

CODE

==================

import java.util.ArrayList;

public class Driver {

  public static void main(String[] args) throws Exception{

      int N = 100000;

      ArrayList<Integer> arr = new ArrayList<>(N);

     

      long startTime = System.currentTimeMillis();

      for(int i=0; i<N; i++) {

          arr.add(i);

          arr.trimToSize();

      }

      long endTime = System.currentTimeMillis();

      double time = (endTime - startTime)/1000;

      System.out.println("Total time taken = " + time + " seconds.");

  }

}

Explanation:

5 0
3 years ago
What is the shortcut to select all text?
abruzzese [7]
Highlight everything with your curser.
7 0
3 years ago
Read 2 more answers
Given an int variable k that has already been declared, use a while loop to print a single line consisting of 88 asterisks. Use
Grace [21]

Answer:

True

Explanation:

The while loop is going to be executed until the condition is false.

Since <em>k</em> is initially equal to 1, the loop will execute 88 times. One asterisk will be printed and <em>k</em> will be incremented by one during each iteration.

When <em>k</em> becomes 89, the condition will be false (89 is not smaller or equal to 88) and the loop will stop.

6 0
2 years ago
What would you have to know about the pivot columns in an augmented matrix in order to know that the linear system is consistent
Scrat [10]

Answer:

The Rouché-Capelli Theorem. This theorem establishes a connection between how a linear system behaves and the ranks of its coefficient matrix (A) and its counterpart the augmented matrix.

rank(A)=rank\left ( \left [ A|B \right ] \right )\:and\:n=rank(A)

Then satisfying this theorem the system is consistent and has one single solution.

Explanation:

1) To answer that, you should have to know The Rouché-Capelli Theorem. This theorem establishes a connection between how a linear system behaves and the ranks of its coefficient matrix (A) and its counterpart the augmented matrix.

rank(A)=rank\left ( \left [ A|B \right ] \right )\:and\:n=rank(A)

rank(A)

Then the system is consistent and has a unique solution.

<em>E.g.</em>

\left\{\begin{matrix}x-3y-2z=6 \\ 2x-4y-3z=8 \\ -3x+6y+8z=-5  \end{matrix}\right.

2) Writing it as Linear system

A=\begin{pmatrix}1 & -3 &-2 \\  2& -4 &-3 \\ -3 &6  &8 \end{pmatrix} B=\begin{pmatrix}6\\ 8\\ 5\end{pmatrix}

rank(A) =\left(\begin{matrix}7 & 0 & 0 \\0 & 7 & 0 \\0 & 0 & 7\end{matrix}\right)=3

3) The Rank (A) is 3 found through Gauss elimination

(A|B)=\begin{pmatrix}1 & -3 &-2  &6 \\  2& -4 &-3  &8 \\  -3&6  &8  &-5 \end{pmatrix}

rank(A|B)=\left(\begin{matrix}1 & -3 & -2 \\0 & 2 & 1 \\0 & 0 & \frac{7}{2}\end{matrix}\right)=3

4) The rank of (A|B) is also equal to 3, found through Gauss elimination:

So this linear system is consistent and has a unique solution.

8 0
3 years ago
What does the hard disk drive do?
Airida [17]
It stores data and retrieving digital information using one or more rigid rapidly rotating disks (platters) coated in magnetic material
4 0
3 years ago
Read 2 more answers
Other questions:
  • When you move a paragraph in a document that includes text with a footnote, what happens to the footnote reference?
    7·2 answers
  • The blank provides access to the internet May also be internal ??
    14·1 answer
  • Computers help eliminate that repetitive of manual task. How can this benefit you in in your overall career
    7·2 answers
  • lance has three tables in his database. He wants to generate a report to show data from the three tables. Therefore, he decides
    7·2 answers
  • . Describe a way to simplify a complex problem.
    8·1 answer
  • 3.5 Code Practice: Question 1<br> (Website: Edhesive)
    14·1 answer
  • Create an application that determines the final cost of food items and non-food items, assuming only non-food items are taxed. T
    8·1 answer
  • I'm showing my friends brainly. Answer with anything so they can see how fast I can get answers.
    10·2 answers
  • 7. Suppose that a RISC machine uses 5 register windows. a. How deep can the procedure calls go before registers must be saved in
    14·1 answer
  • You have a Windows system that has both wired and wireless network connections. The wired connection is on the internal private
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!