Adding elements to a sorted array list with binary search

[megascruples]

Im supposed to use binary to add to the list and keep it in order. Im not sure if im doing it right, but I cant seem to get it to add to the list at all. Any help would be appreciated.

template<class T>
int SortedArrayList<T>::add(T* element) {
	if (element == NULL) {
		return -1;
	}

	bool notBigEnough = (maxLength == length);
	if (notBigEnough) {
		resize();
	}
	// TODO
	int first = 0;
	int last = length-1;
	int mid = first+((last-first)/2);

	while(first <= last){
		if(*element == *elements[mid]) {
			*elements[mid] = *element;
			return mid + 1;
		}

		else if(*element < *elements[mid]) {
			last = mid - 1;
		}

		else if (*element > *elements[mid]) {
			first = mid + 1;
		}
		mid = first+((last-first)/2);
	}
	return mid + 1;
}

[keskiverto]

It could be better to do the operation in two steps:
1. Locate the insertion position.
2. Insert at that position.

As is, it remains unclear how the assignment operator on line 18 does an insertion. Intuitively, an assignment changes rather than adds. Besides, the value does not even change because of the condition on line 17.

Furthermore, there is nothing that looks like insertion, if the new value is novel.


PS. What is the function of the returned value?

[megascruples]

Okay i see what i did and ive made some changes. Its still not adding to the list though. She wants the position returned for the google test she has set up or something like that

template<class T>
int SortedArrayList<T>::add(T* element) {
	if (element == NULL) {
		return -1;
	}

	bool notBigEnough = (maxLength == length);
	if (notBigEnough) {
		resize();
	}
	// TODO
	int position;
	int first = 0;
	int last = length;
	int mid = first+((last-first)/2);

	while(first <= last){
		if(*element == *elements[mid]) {
			 position = mid;
			 break;
		}

		else if(*element < *elements[mid]) {
			last = mid - 1;
		}

		else if (*element > *elements[mid]) {
			first = mid + 1;
		}
		mid = first+((last-first)/2);
	}

	for (int i = length; i >= position; i--)
		elements[i + 1] = elements[i];

	elements[position] = element;
	length++;

	return position + 1;
}

[keskiverto]

Lets say that the list has {2,3} and the value to add is -1.
first=0, last=2, mid=1

The -1 != 3.
-1 < 3, so last = 0 and mid = 0.

first <= last and thus a new iteration:
The -1 != 2.
-1 < 2, so last = -1.

Now first > last --> no more iterations.

The the value of 'position' was not initialized nor changed at any point.


In other words: your binary search sets the position ONLY IF the list already contains equal value.


Even simpler special case: the list is empty. Where do you add?

[megascruples]

Okay i see what you mean but i dont know how to fix it

[keskiverto]

Draw inspiration from http://www.cplusplus.com/reference/algorithm/upper_bound/

[megascruples]

Got it thanks!