From the link in your comment on your OP:
Range_lookup A logical value that specifies whether you want VLOOKUP to find an exact match or an approximate match:
If TRUE or omitted, an exact or approximate match is returned. If an exact match is not found, the next largest value that is less than lookup_value is returned.
The values in the first column of table_array must be placed in ascending sort order; otherwise, VLOOKUP may not give the correct value. You can put the values in ascending order by choosing the Sort command from the Data menu and selecting Ascending. For more information, see Default sort orders.
If FALSE, VLOOKUP will only find an exact match. In this case, the values in the first column of table_array do not need to be sorted. If there are two or more values in the first column of table_array that match the lookup_value, the first value found is used. If an exact match is not found, the error value #N/A is returned.
It isn't terribly obvious the way that document is formatted, but the qualification that the lookup range must be sorted ascending only applies for when the 4th argument in VLOOKUP is TRUE, or a non-zero positive number, or omitted. (If the 4th argument is a non-zero negative number, the first column must be sorted descending.) In these cases, you are allowing the formula to return a non-exact match.
If you are looking for an exact match only, then you must specify FALSE (or zero) for the 4th argument, and the first column needn't be sorted at all.
If you are looking for an non-exact match on an unsorted range, then something like this should work in Google Sheets (assuming you are looking for a match of C1 in column A, and returning the corresponding entry in column B):
=INDEX(SORT(FILTER(A:B;LEN(A:A));1;1);MATCH(C1;SORT(FILTER(A:A;LEN(A:A));1;1));2)