JAVA The binary Search algorithm can be used with any indexed linear structure s

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.ArrayList;

public class BinarySearch {

   public static <E extends Comparable<E>> int LLBS(ArrayList<E> list, E search) {
      
       int low = 0;
       int high = list.size()-1;
      
       while(low <= high){
          
           int mid = (low + high) / 2;
          
           if (list.get(mid).compareTo(search) == 0) { // found target
               return mid;
           } else if (list.get(mid).compareTo(search) < 0) { // too low; go right
               low = mid+1;
           } else {
               high = mid-1; // go left
           }
       }
      
       return -1; // did not found
   }
  
   public static void main(String[] args) {
      
       ArrayList<Integer> list = new ArrayList<Integer>();
       list.add(-2);
       list.add(8);
       list.add(13);
       list.add(22);
       list.add(25);
       list.add(38);
       list.add(42);
       list.add(51);
       list.add(103);
      
       System.out.println("Returned Value: "+LLBS(list, 9));
       System.out.println();
   }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.