In most cases, I would say #4:
- Return a status code indicating whether the operation succeeded or failed and return the index by reference (either using references or a pointer depending on your version of C).
The advantages of #4 over #3 are:
When you need a function to return more than one value, just add more reference parameters for the values you need to return.
If your C functions always return status codes everywhere in your program, then you always know that the return code is status.
It does not eat into your value space for the return index (or other data types) that your function returns and avoids magic number constants. (For example, if you were returning a temperature value in Celsius, 0 and -1 are both valid as are any positive numbers. You might return -274 as invalid, but that is a little obtuse.)
The return code can give a reason for failure or success more than just a Boolean success or failure in a pretty straightforward way.
OTOH, if you program is pretty small, and you don't mind a few magic constants, then either #1 or #2 are morally equivalent and can make for less typing than #3 or #4. #2 has a few advantages over #1:
As mentioned in other answers, a signed int return value can only represent half of the numbers an unsigned int can represent.
It avoids signed vs. unsigned comparison issues if you are comparing against sizeof(array), std::vector::string, which are size_t. Most often the issue is a compiler warning gets ignored (leading people to generally ignore warnings when they should not) or someone fixes it with a cast, hopefully after analyzing to make sure that the cast is really valid.
I have personally used #1, #2, and #4 and find the #4 scales the best. I tend to default to #4, especially in code where failures are common and need to be handled. Either 1 or 2 usually work out best if the code is smaller and you are calling a lot of routines that return one thing and cannot fail (e.g., image processing routines).