Getting partition boundaries in sorted integer array using only equalTo operator

Question

For my task, I need to find partition boundaries in sorted input. Values are expected to be repeated, I just need to find range for each value. Please check comment in following output for example. For some reason, I can not use < or> operation, I only have equality operator.

/*
Input:
Index : Value
0 : 1
1 : 1
2 : 1
3 : 2
4 : 2
5 : 2
6 : 2
Output:
Value 1 is till 2 index
Value 2 is till 6 index
 */
 public void printPartitionBoundaries(ArrayList<Integer> array)
 {
 int f = 0;
 int l = array.size()-1;
 while (f < l) {
 int cp = ((Integer)array.get(f)).intValue();
 int of = f;
 boolean done = false;
 while (!done)
 {
 int m = (f + l)/2;
 if ((l-f) <= 1) {
 if ( l == array.size() -1 )
 System.out.println("Value " + cp + " is till " + l + " index");
 else
 System.out.println("Value " + cp + " is till " + (l-1) + " index");
 done = true;
 break;
 }
 if (array.get(f).equals(array.get(l)) == false) {
 if (array.get(f).equals(array.get(m)) == false)
 l = m;
 else
 f = m;
 } else {
 f = m;
 }
 }
 f = l;
 l = array.size()-1;
 }
 }

Answer 1

In general single letter variables are okay, but here short names like first and last would be more readable.

Also java has a very strong convention of always using braces {}, and an indentation of 4 spaces. (Historically C/C++ had normally 3, and one whished less nesting of code due to the "superior" quality of the new language.)

List as interface is more generic than ArrayList, so do not overspecify, be too restrictive.

Using an exclusive upperbound is often done in computer science, and indeed in the java APIs themselve. Here it would mean having partions [f, l> like [a, b>, [b, c>, [c, d>, [d, e>. So at the end of the range searching loop f = l;.

 public void printPartitionBoundaries(List<Integer> array)
 {
 int f = 0;
 int l = array.size(); // Upperbound exclusive
 while (f < l) {
 int cp = array.get(f);

of (old first) is a leftover.

The loop with done: done could be removed, a while (true) would work as well. Hence use the first if-condition as while-condition.

Also m was calculated too early.

Also == false and == true should really not be seen.

The nested ifs can be simplified.

Mind that the condition treats two cases of 1 element and 0 elements. Simpler would be while (f < l).

 while ((l-f) > 1)
 {
 int m = (f + l)/2;
 if (!array.get(f).equals(array.get(l))
 && !array.get(f).equals(array.get(m))) {
 l = m;
 } else {
 f = m;
 }
 }

I wonder about the correctness; somehow one expects f = m + 1; to have a loop variant (l-f) diminishing every step.

The following if-statement on l == array.size() should become:

 System.out.println("Value " + cp + " is till " + (l-1) + " index");

Check, maybe the while-condition should become > 0, and extra step more.

 f = l;
 l = array.size();
 }
 }

To verify the correctness I leave up to you yourself.

---

Resulting code:

 public void printPartitionBoundaries(List<Integer> array)
 {
 int f = 0;
 int l = array.size(); // Upperbound exclusive
 while (f < l) { // f != l
 int cp = array.get(f);
 while ((l-f) > 1) // maybe better f != l too
 {
 int m = (f + l)/2;
 if (!array.get(f).equals(array.get(l))
 && !array.get(f).equals(array.get(m))) {
 l = m;
 } else {
 f = m;
 }
 }
 System.out.println("Value " + cp + " is till " + (l-1) + " index");
 f = l;
 l = array.size();
 }
 }