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

Question

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] · Answer 1 · 2022-10-23T11:52:47+03:00

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;