I am trying to binary search through a linked list of strings. However, my binar
ID: 3691473 • Letter: I
Question
I am trying to binary search through a linked list of strings. However, my binary search algorithm doesn't work. If someone can fix my binary search algorithm in my code, I would appreciate it.
package binarysearch;
public class LinkedList<E> {
private Node head;
private int listCount;
public LinkedList() {
head = new Node(null);
listCount = 0;
}
public void getHead()
{
head = new Node(null);
}
/*
* Appends the specified element to the end of this list.
* Precondition: The element had been created.
* Postcondition: The elements had been added into linkedlist.
* @param data: The elements being added.
*/
public void add(String data)
{
Node temp = new Node(data);
Node current = head;
while (current.getNext() != null) {
current = current.getNext();
}
current.setNext(temp);
listCount++;
}
/*
* Inserts the specified element at the specified position in this list.
* Precondition: The elements had been created.
* Postcondition: The elements had been added at the certain index of linkedlist.
* @param data: The elements being adding in linkedlist.
* @param index: The index in the linkedlist
*/
public void add(String data, int index)
{
Node temp = new Node(data);
Node current = head;
for (int i = 1; i < index && current.getNext() != null; i++) {
current = current.getNext();
}
temp.setNext(current.getNext());
current.setNext(temp);
listCount++;
}
/*
* Returns the element at the specified position in this list.
* Precondition: There is elements in the list.
* Postcondition: The elements had been found in list.
* @param index: The index of the element being look.
* @return The value of the elements being look for.
*/
public String get(int index)
{
if (index <= 0)
return null;
Node current = head.getNext();
for (int i = 1; i < index; i++) {
if (current.getNext() == null)
return null;
current = current.getNext();
}
return current.getData();
}
/*
* Removes the element at the specified position in this list.
*/
public boolean remove(int index)
{
if (index < 1 || index > size())
return false;
Node current = head;
for (int i = 1; i < index; i++) {
if (current.getNext() == null)
return false;
current = current.getNext();
}
current.setNext(current.getNext().getNext());
listCount--;
return true;
}
/*
* Returns the number of elements in this list.
* Precondition: There is elements in list.
* Postcondition: The size of the list had been determined.
* @return the number of elements in this list.
*/
public int size()
{
return listCount;
}
/*
* Going through the list.
* Precondition: There is elements in the list.
* Postcondition: The list had been transerved.
* @return output: The elements in the list.
*
*/
public String toString() {
Node current = head.getNext();
String output = "";
while (current != null) {
output += " " + current.getData().toString() + " ";
current = current.getNext();
}
return output;
}
/*
* Setting up the Node
*/
private class Node {
Node next;
String data;
public Node(String _data) {
next = null;
data = _data;
}
public Node(String _data, Node _next) {
next = _next;
data = _data;
}
public String getData() {
return data;
}
public void setData(String _data) {
data = _data;
}
public Node getNext() {
return next;
}
public void setNext(Node _next) {
next = _next;
}
}
}
package binarysearch;
public class SearchableLinkedList<E extends Comparable<E>> extends LinkedList<String> {
SearchableLinkedList() {
super();
}
/*
* Searching for a certain String elements in linkedlist Precondition: There
* is elements in linkedlist. Postcondition: The certain element in
* linkedlist had been found.
*
* @return mid: the index of the certain element being search
*
* @param list, key, start, end
*/
public int binarySearch(LinkedList<String> list, int start, int end, String key) {
if (list.size() == 1) {
return 1;
}
int end1 = list.size() -1;
int mid = (start + end1) / 2;
if (list.get(mid).compareTo(key) < 0) {
return binarySearch(list, start, mid - 1, key);
} else if (list.get(mid).compareTo(key) > 0) {
return binarySearch(list, mid + 1, end, key);
} else
return mid;
}
}
package binarysearch;
public class MainDriver {
/*
* Executing the Linkedlist and SearchableLinkedList class.
*/
public static <E >void main(String [] args){
LinkedList<String> list = new LinkedList<String>();
SearchableLinkedList<String> s = new SearchableLinkedList<String>();
list.add("Bob");
list.add("Chris");
list.add("Evan");
list.add("Duck");
list.add("Zack");
list.add("David");
System.out.println(list.toString());
System.out.println("Size of the list element is: " + list.size());
System.out.println("Found Zack at: " + s.binarySearch(list, 0 , 5, "Zack"));
}
}
Explanation / Answer
Hi, I have fixed your code.
Index starts from 1 (not 0).
class LinkedList<E> {
private Node head;
private int listCount;
public LinkedList() {
head = new Node(null);
listCount = 0;
}
public void getHead()
{
head = new Node(null);
}
/*
* Appends the specified element to the end of this list.
* Precondition: The element had been created.
* Postcondition: The elements had been added into linkedlist.
* @param data: The elements being added.
*/
public void add(String data)
{
Node temp = new Node(data);
Node current = head;
while (current.getNext() != null) {
current = current.getNext();
}
current.setNext(temp);
listCount++;
}
/*
* Inserts the specified element at the specified position in this list.
* Precondition: The elements had been created.
* Postcondition: The elements had been added at the certain index of linkedlist.
* @param data: The elements being adding in linkedlist.
* @param index: The index in the linkedlist
*/
public void add(String data, int index)
{
Node temp = new Node(data);
Node current = head;
for (int i = 1; i < index && current.getNext() != null; i++) {
current = current.getNext();
}
temp.setNext(current.getNext());
current.setNext(temp);
listCount++;
}
/*
* Returns the element at the specified position in this list.
* Precondition: There is elements in the list.
* Postcondition: The elements had been found in list.
* @param index: The index of the element being look.
* @return The value of the elements being look for.
*/
public String get(int index)
{
if (index <= 0)
return null;
Node current = head.getNext();
for (int i = 1; i < index; i++) {
if (current.getNext() == null)
return null;
current = current.getNext();
}
return current.getData();
}
/*
* Removes the element at the specified position in this list.
*/
public boolean remove(int index)
{
if (index < 1 || index > size())
return false;
Node current = head;
for (int i = 1; i < index; i++) {
if (current.getNext() == null)
return false;
current = current.getNext();
}
current.setNext(current.getNext().getNext());
listCount--;
return true;
}
/*
* Returns the number of elements in this list.
* Precondition: There is elements in list.
* Postcondition: The size of the list had been determined.
* @return the number of elements in this list.
*/
public int size()
{
return listCount;
}
/*
* Going through the list.
* Precondition: There is elements in the list.
* Postcondition: The list had been transerved.
* @return output: The elements in the list.
*
*/
public String toString() {
Node current = head.getNext();
String output = "";
while (current != null) {
output += " " + current.getData().toString() + " ";
current = current.getNext();
}
return output;
}
/*
* Setting up the Node
*/
private class Node {
Node next;
String data;
public Node(String _data) {
next = null;
data = _data;
}
public Node(String _data, Node _next) {
next = _next;
data = _data;
}
public String getData() {
return data;
}
public void setData(String _data) {
data = _data;
}
public Node getNext() {
return next;
}
public void setNext(Node _next) {
next = _next;
}
}
}
class SearchableLinkedList<E extends Comparable<E>> extends LinkedList<String> {
SearchableLinkedList() {
super();
}
/*
* Searching for a certain String elements in linkedlist Precondition: There
* is elements in linkedlist. Postcondition: The certain element in
* linkedlist had been found.
*
* @return mid: the index of the certain element being search
*
* @param list, key, start, end
*/
public int binarySearch(LinkedList<String> list, int start, int end, String key) {
//System.out.println("S: "+start+", E: "+end);
if (list.size() == 1) {
return 1;
}
//int end1 = list.size() -1;
int mid = (start + end) / 2;
if (list.get(mid).compareTo(key) > 0) {
return binarySearch(list, start, mid - 1, key);
} else if (list.get(mid).compareTo(key) < 0) {
return binarySearch(list, mid + 1, end, key);
} else
return mid;
}
}
class MainDriver {
/*
* Executing the Linkedlist and SearchableLinkedList class.
*/
public static <E >void main(String [] args){
LinkedList<String> list = new LinkedList<String>();
SearchableLinkedList<String> s = new SearchableLinkedList<String>();
list.add("Bob");
list.add("Chris");
list.add("Evan");
list.add("Duck");
list.add("Zack");
list.add("David");
System.out.println(list.toString());
System.out.println("Size of the list element is: " + list.size());
System.out.println("Found Zack at: " + s.binarySearch(list, 1 , 6, "Zack"));
}
}
/*
Output:
Bob Chris Evan Duck Zack David
Size of the list element is: 6
Found Zack at: 5
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.