JAVA The binary Search algorithm can be used with any indexed linear structure s
ID: 3697940 • Letter: J
Question
JAVA
The binary Search algorithm can be used with any indexed linear structure such as an array.
ArrayList, or LinkedList. The algorithm can be started as:
While the value being searched for isn’t found and the search space is not exhausted, check the middle element for the value. If it is found return the index where it was found, if it is not found remove either the lower or upper half of the current search space from the search space based upon the middle value’s relationship with the search value. If the value is not in the list return -1.
The ArrayList<E> defined in the java.util package has the following methods:
Int size() – returns the number of elements in the list
E get(int) – returns the item at the passed index
Write a method that applies the Binary search to a sorted LinkedList of Comparable elements. The header is:
public static <E extends Comparable<E>> int LLBS(ArrayList<E> list, E search)
Explanation / Answer
import java.util.*;
public class BinarySearch<E> {
public static <E extends Comparable<E>> int LLBS(ArrayList<E> list, E search)
{
if(list.isEmpty()==true)
{
return -1;
}
int mid=list.size()/2;
E midElement=list.get(mid);
if(search.compareTo(midElement)==0)
{
return mid;
}
else if(search.compareTo(midElement)>0)
{
//reducing the size of list by clearing the elements from 0 to mid
list.subList(0,mid+1).clear();
return mid+LLBS(list,search);
}
else
{
//reducing the size of list by clearing the elements from 0 to mid
list.subList(mid,list.size()).clear();
return LLBS(list,search);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.