-1

I have certain preconditions on input data and I need to design an algorithm for that data. Should I also handle invalid preconditions? Also is it normal that my algorithm will work only for a certain number of inputs, for example 4, and for any smaller number of inputs I'll have "if input.size" clause?

To clarify my question. Well, actually it's a task from a book but anyway. So it says i'm given an array sorted, then swapped so that it looks like "4567123" first part "123" is swapped. So, should I bother to design algoritm for non-swaped case? Also my algoritm doesn't work well for input size 1, 2, 3, so I inserted cases for 1 , 2 ,3. Is it ok. So here is the code:

//file SwapedArraySearch.java\
public class SwapedArraySearch {
    public static int search(int[] arr) {
        switch (arr.length){
            case 1:
                return arr[0];
            case 2:
                return arr[0] > arr[1]?arr[1]:arr[0];
            case 3:
                return arr[0] > arr [1] ? (arr[1] > arr[2]?arr[2]: arr[1]):
                                            (arr[0] > arr[2]?arr[2]: arr[0]);
        }
        int x = arr[0];
        int n = arr.length/2;
        int prevn = arr[n] > x ? arr.length -1 : 1; 
        int t;
        while(prevn != n) {
            if (x < arr[n]) {
               if (arr[n] > arr [n + 1] )
                   return arr[n+1];
                t = n;
                n = n + (prevn - n)/2;
                prevn = t;
            } else {
                if (arr[n - 1] > arr[n])
                    return arr[n];
                t = n;
                n = prevn + (n - prevn)/2;
                prevn = t;
            }
        }
        return arr[0] > arr[1] ? arr[arr.length - 1] : arr[0];
    }

    public static void main(String... args) {
        int[] arr = new int[args.length];
        for (int i = 0; i < args.length; i++)
            arr[i] = Integer.valueOf(args[i]);
        System.out.println(search(arr));            
    }
}

Also I'm bother that it looks too complex. Doesn't it or is it fine?

Also, let's say, binary search, it obviously shouldn't check before run that array was sorted before, right?

dhblah
  • 339
  • 1
  • 3
  • 11

1 Answers1

1

First you need to distinguish your algorithm and your implementation of this algorithm: the algorithm must consider all the possible cases while your implementation can assume there is a more restrictive context.

Practically there are different strategies you can adopt. First, you can consider that the inputs may be not well formatted (invalid string, negative numbers, too small list, etc.), and it's your problem. Then it's your job to take these issues into account and to act appropriately. This will improve the robustness ( the ability to behave smartly under special circumstances) of your implementation. In case of problem, you will typically raise an exception or return a particular value to indicate the problem.

Another strategy consists in programming using contracts. Each of your methods has a contract having a specification for the inputs and the outputs. In the input part, the data that must be given to the method is specified. For instance, you can write "the list must have at least four elements, and all the elements in the list must be positive. The output part describes what the method will retrieve if the input part of the contract is respected. For instance "the minimal value of the elements is retrieved". If the input part is not respected, the method is free to act as it wants: it can return an arbitrary value, raise an exception , etc. If the client does not respect its part of the contract, the method does not have to respect its own.

Contract programming can be implemented with languages that support it (for instance, Eiffel) or by using conventions + an assert mechanism.

mgoeminne
  • 1,158
  • 6
  • 11