Я пытаюсь реализовать метод двоичной вставки.
В настоящее время этот метод очень прост, он принимает аргумент, в цикле while он ищет элемент, который больше, чем аргумент (в данном случае String, который является фамилией человека), он ломается, как только находит его и сдвигает остальную часть массива вправо. Затем аргумент вставляется в позицию разрыва.
Я попытался изменить его на тот, который будет искать позицию вставки, заимствовав из алгоритма двоичного поиска. Однако я просто не могу заставить его работать.
Не могли бы вы сообщить мне, что я делаю неправильно? Вот мой код:
public void insert(Person person)
{
String lastName = person.getLastName();
int position = -1; // the position from which the array will be shifted to the right and where the argument will be inserted, will be assigned properly below
int lowerBound = 0;
int upperBound = numElems - 1;
int currIt;
if (numElems == 0)
array[0] = person; // if array empty insert at first position
else
{
while (true)
{
currIt = (lowerBound + upperBound) / 2; //the item to compare with
int result2 = 0;
int result1 = array[currIt].getLastName().compareTo(lastName);
if (array[currIt+1] != null) // if the next element is not null, compare the argument to it
result2 = array[currIt+1].getLastName().compareTo(lastName);
if (currIt == 0 && result1 > 0) // this is when the argument is smaller then the first array element
{
position = 0;
break;
}
// if the position to insert is the last one, or we have found a suitable position between a smaller and a bigger element
else if ( (result1 < 0 && (currIt == numElems-1)) || (result1 < 0 && result2 > 0) ) {
position = currIt+1;
break;
}
else
{
if (result1 < 0) // the place to put it should be in the upper half
lowerBound = currIt + 1;
else
upperBound = currIt - 1; //in the lower half
}
}
}
// position has been set to anything else other -1, then we have found our spot, probably a redundant check but useful for debugging
if (position != -1)
{
//shift array to the right and insert element
for (int j = numElems; j > position; j--)
array[j] = array[j-1];
System.out.println("Inserted an element");
array[position] = person;
numElems++;
}
}
arr.insert(new Person("Charles", "Dickens", 23));arr.insert(new Person("Adam", "Bay", 29)); arr.insert(new Person("Ethan", "Fowler", 18));
я надеялся расположить их по фамилиям (Bay...); Это прекрасно работает:String lastName = person.getLastName(); int i; for (i = 0; i < numElems; i++) if (array[i].getLastName().compareTo(lastName) > 0) break; for (int j = numElems; j > i; j--) array[j] = array[j-1]; array[i] = person; numElems++;
Но хотелось ускорить :) - person Nobilis   schedule 06.09.2012