Why does the return of the linear search for the element not found have to be -1?

Asked

Viewed 70 times

7

Why should I return -1 at the end of a linear search if the element was not found? 

int linearSearch(int[] list, int size, int key){
        for(int index=0; index<size; index++)
          if(list[index]==key)
            return index;
        return -1;
      }//linearSearch
java array

2 answers

7


You don’t have to do this, you can do a lot of things, but you have to report in some way that you haven’t found the element you’re looking for. One of the most commonly used ways is to return a value that would be impossible in a search that finds the element, and usually a negative is adequate, the -1 is agreed to have a certain consistency.

Some people criticize that sort of thing. I’m an advocate whenever it makes sense, as seems to be the case.

  • The problem of mixing valid returns and error codes is that there is nothing in the type system that distinguishes between the two. In these cases it is preferable to choose to make an exception or to return a monad whose semantics indicate the possibility of there is no a valid value. Specifically in the linear search function, the use of the -1 It’s so common it’s already stuck in people’s heads, so it’s acceptable, but I’d rather use a monad. Your linked post is pretty cool and expands the subject well.

  • 1

    This is your opinion, and you can have it, but essentially all languages/libraries chose to do it differently, even the most modern that already had the mantra of the "bid exception" (which in my opinion and many people’s, is wrong in most situations, and we don’t like mantras, but facts). Virtually every language has pragmatic typing and full of gaps, people have to deal with it. A type system that really doesn’t let anything go wrong makes language impractical. Languages that abuse the exception and suffer c/performance and creates other problems

  • All languages?

  • essentially

  • The use of -1 to indicate the absence of an index is very seductive because it is something very simple and works well in almost all cases. It is not a problem in my opinion. However, there are languages with type systems that provide easy handling of these situations in a more semantic way, and I appreciate that. (1/3)

  • In the case of linear search, we all know we are prepared to receive a -1 as a return, but when we are maintaining a giant codebase, it is very nice when the programmer before us wrote int? instead of just int to make clear that the method buscarReferenciaPlaca may not return a valid integer (especially when dealing with a SOAP API, for example). (2/3)

  • I reiterate: I don’t think I use -1 in the case of linear search is a problem, but I appreciate the use of more semantic tools for this kind of situation. Fsharp is a beautiful example of this, where there is the function findIndex and tryFindIndex, that launches an Exception and returns a monad, respectively, if the index is not found. This greatly facilitates function composition. I’m not saying you’re wrong, I’m just extending the subject to people who read your answer. (3/3)

Show 2 more comments

0

Here you can also opt for other solutions such as throwing an exception when the search fails, or passing a flag by a flag that makes an effect similar to the return of -1. However this last solution is not recommended for various reasons.

Basically, as Maniero said, the important thing is that you have the indication that you did not find and that this information does not present doubts.

Browser other questions tagged java array

You are not signed in. Login or sign up in order to post.