2
$\begingroup$

Here is the linear search algorithm provided in class:

bool LinearSearch(int [] a, int l, int u, int e) { 
      for(int i:=l; i ≤ u ; i := i + 1) {
          if (a[i] = e) return true;
      }
      return false;
}

If the intention of this function was to linear search through the function why allow a parameter of l and u? A user could test this function in ways to breach the intention of linear search. For example let l and u be numbers such that it only searches through a subsequence of the list and not the entire list. I asked my professor if the intention of this code was to have the possibility of it being used in ways that do not search the entire list. She didn't quite understand me, because she replied "No, it should be possible to search through the entire list." Well I know it's possible but why have the l and u if you can just write the code better and remove l and u. Now I know in other languages you might need to know the bounds, but this isn't a programming class whatsoever.

$\endgroup$

1 Answer 1

2
$\begingroup$

Surely, it is not about correctness. It is only a slightly general version of linear search. This technique is not uncommon. Obviously the more general the procedure is, the more applicable it is.

Linear search is a little bit simple for an illustration. Let's look at quicksort@wiki that is declared as quicksort(A, lo, hi). This is because quicksort is a recursive procedure that needs to call itself over a sub-range of the array. Notice that quicksort also needs a partition procedure, which is declared as partition(A, lo, hi) instead of partition(A).

Another kind of examples is dynamic programming. Suppose that you want to compute the edit distance@wiki between two strings of $a$ and $b$, with lengths $m$ and $n$ respectively. What you are actually computing is $\text{Dist}(i,j)$ for $0 \le i \le m, 0 \le j \le n$.

$\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.