1
\$\begingroup\$

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;
      }
   }
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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();
      }
   }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.