0
Мне нужна помощь в добавлении метода двоичного поиска в упорядоченный связанный список. Вот код, который у меня есть до сих пор, но я застрял в этой части. Я смущен тем, как принимать значения, добавленные с помощью метода insert, а затем выполнять поиск по нему, а затем указать, в какой позиции находится элемент. Вот программа, которую я имею до сих пор:Двоичный поиск по заказу связанного списка
import java.util.LinkedList;
class List {
public List next;
public List previous;
public long data;
public Link(long d) {
data = d;
}
public void displayLink() {
System.out.print(data + " ");
}
}
class OLinkList {
private LinkedList first;
private LinkedList last;
public OLinkList() {
first = null;
last = null;
}
public boolean isEmpty() {
return first == null;
}
public void insert(long num) {
List newLink = new List(num);
if (first == null) {
first = newLink;
last = newLink;
} else {
last.next = newLink;
last = newLink;
}
}
}
Теперь у меня есть идея, как работает бинарный поиск. Как я могу взять что-то вроде этого и применить его к коду, который у меня есть?
public int binarySearch(int[] a, int x) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high)/2;
if (a[mid] == x) return mid;
else if (a[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}
Обратите внимание, что для двоичного поиска требуется произвольный доступ к произвольным элементам. Это не так в связанном списке. – Joey
После принятия совета Джои для вашего сердца, преобразования вашего списка в массив (с использованием метода .toArray LinkedList). Используйте метод Java binarySearch по умолчанию Arrays.binarySearch (см. Http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html). Примечание: Поскольку вызов toArray в списке принимает O (n), это имеет смысл только при выполнении нескольких запросов. – quant
Я не понимаю, как упорядочен ваш связанный список –