Findfirst on sorted array

General Usage
1

I have a sorted array of numbers:

A = [1, 4, 10, 15, 18]

I want to determine the first index where a value, v, occurs in this array (or 0 if it does not occur), like findfirst(A, v). But I want to exploit the fact that A is already sorted (binary search). Is this already implemented in Julia? I did not find anything on the docs for findfirst.

2

Try searchsortedfirst.

Also, please learn how to use the help system (apropos("sorted") would have worked), and make a minimal effort to find answers before posting.

6 Likes
3

Pointing out apropos("sorted") seems useful, but the rest of the answer seems unnecessarily hostile to me. It’s pretty important for growing languages to be welcoming to newcomers.

9 Likes
4

Woo never noticed the apropos function :smile: , for sure you are welcome @bramtayl .

1 Like
5

This is very important though I don’t think this is a case where this rule is violated.
Reading doc string, simple search of doc and google should definitely be done, but it’s pretty hard to put together the correct search terms for either google or our doc to return the right result in this case. Combinations of sorted, find, first does not return the right function for each.

We could raise the requirement to include apropos though a much more user friendly interface must be provided for that. (Preferably an online or interactive interface, I don’t think people will try to type keywords into the REPL help mode especially when multiple keyword doesn’t work there)

7 Likes
6

In Matlab (and I think also Python) each docstring includes a "See also… " section. In Matlab, the “See also” function names are clickable links to more docstrings. I find that I am rarely more than a couple of “see also” clicks away from the function I’m looking for. It’s pretty useful.

Despite having heard about it a dozen times at least, I always forget about the apropos function, or its name.

1 Like
7

There are also “See also”-s in Julia documentation (clickable to what is referred). Still not too many but it is increasing steadily. Help with this is appreciated.

1 Like
8

I also tend to forget apropos. What is the rationale for the name apropos? If I understood this maybe it would stick.

9

Perhaps useful links:

3 Likes
10

One of the best things about Python is that every possible dumb question has been asked on Stack Overflow, so google gives the right answer straight-away, on top of two exact-match SO posts. Julia is significantly worse in my experience.

11

This was not my intention — if my tone came across as hostile, I apologize.

The names for this family of functions could be better organized, see
https://github.com/JuliaLang/julia/issues/10593

2 Likes
12

Concerning the searchsortedfirst, we must note that the function does not return a value which is by itself indicative of a non-match. I think we should add that to verify if the element is or not in the list, we should add a test afterwards:

x = [ 1, 2, 3, 5 ]
function my_searchsortedfirst(x,i)
  index = searchsortedfirst(x,i)
  if index > lastindex(x) || x[index] != i
    return 0
  else
    return index
  end
end

julia> my_searchsortedfirst(x,4)
0
1 Like
13

To obtain a value that is indicative of a non-match, you can use searchsorted, instead of searchsortedfirst.

(P.S. I’m not sure that this minor detail deserved reviving a thread that was created years ago! I think it would have been better to create a new post, maybe linking back to this one.)

2 Likes
14

Well, I didn’t have any question, actually. However, while searching for a solution, I found this thread, probably indicated by the search engines. While reading it, I noticed that the original question was not completely answered and it would be useful to have it better explained.

(also the output of searchsorted still needs to be interpreted, and finding the first occurrence is faster than all occurrences).

15

Well, it depends on how you see it: the pointer to searchsortedfirst did not answer it completely, but the advice of looking on apropos("sorted") did. :wink:

Regarding the output of searchsorted, I think that 1:0, 3:2, etc. are as easy to interpret as a “non-match” as 0. (EDIT: to clarify this statement, you only need to check if the length of that output is zero, which is a very cheap operation.) And I’m not sure about efficiency, but I guess that finding the first and last occurrences of a specific value in a sorted collection (with binary search) is not much more expensive than finding only the first one.