There are lots of approaches to this and while I do agree with Becuzz to some degree that you should usually follow the conventions of the language/team, it's not always completely cut-and-dried. In java, there are competing ideas about the best way to approach this kind of thing and what the right answer is depends on the context of the method.
One thing that I would first try to disabuse you of is that returning -1 is a 'random' value or magic number. You really should not be coding to the specific value. In that case, you should check for values less than 0 for not found. I've seen assumptions like that lead to bugs. For example, in Java
Integer.compare is implemented using subtraction. That means pretty much any int (positive or negative) may be returned but I've seen code that assumes compare calls will only return -1, 0, or 1. Another case in point is
Arrays.binarySearch which, when an element is not found returns a negative number indicating where the element would be in the order if it were in the array.
These kinds of approaches are useful because they return more information that simply "not found". There are other cases though different approaches are common. For example, a method meant to retrieve a collection of items meeting a certain criteria could return a
null. Another option is to return an empty collection. In most cases, the latter is preferable because you don't have to worry about null-pointer checks and there are usually no checks required if all you want to do is iterate over the results. Returning
null is common and expected in Java but it's also problematic. Another option would be to throw an exception but that is generally discouraged because of the overhead of creating a stack trace which is usually overstated but real.
The point is You don't need to blindly follow convention if you can achieve superior results. But in lieu of that, do what people expect.