It's a parallel linear search, with an over-complicated way to divide up the array into a power-of-2 number of chunks. (Since you only split in half with multiple levels of recursion, instead of the usual chunk_size = n/cores_available which can keep all cores busy even if their number isn't a power of 2.)
In terms of algorithmic complexity, it's the same as a typical parallel linear search with cores_available rounded down to a power of 2. The differences are in the engineering choices for starting threads and looping over a chunk of an array in two directions.
It doesn't require any extra space, unless you count the overhead of the OS tracking extra threads. Or if you're counting how much memory in the existing array it touches that a simple linear search from the start wouldn't. (But with cancellation, if the match is uniformly placed, on average it will touch about the same amount since it'll typically be found about half-way through each thread's search chunk. So cancellation latency will let them touch a bit more.)
Looping both ways vs. the standard increasing-address direction
If bidirectional meet-in-the-middle looping was a faster on real CPUs, we'd hopefully already be doing it for all kinds of problems like array sums and dot-products, and a[i] = f(b[i]) problems like level 1 BLAS operations. (And compilers would be optimizing simple loops into loops that went both ways.) It's worth measuring to see if this has any advantages on any mainstream CPUs; perhaps this is something compilers should start doing!
(Compilers probably won't auto-vectorize as easily if you write the source code to loop both ways. Current compilers won't auto-vectorize search loops at all, only loops whose trip-count can be calculated ahead of the first iteration. So they only auto-vectorize loops where they can already tell that the loop touches every element in a range once; other loop optimizations could be conditional on that. You can write a search that always touches all elements, updating a found_position you check at the end. That can be appropriate for tiny arrays, especially fixed-size, both to avoid branch misprediction and to work around the inability of current compilers to make asm that searches efficiently the way hand-written libc memchr does, e.g. with x86 pcmpeqb / pmovmskb to get a bitmask of 16 byte-compare results that you can branch on. SIMD linear search with no data-dependent branching can even be optimal for small sorted arrays, although that enables tricks like counting elements where a[i] < key which is faster than blending match positions.)
Searching both ways from the starting point makes sure you read the whole cache line while it's still hot. But doing so from different CPU cores (thread) only benefits from an outer level of shared cache (e.g. L3) if the two cores share any cache at all. (Which they might not on a multi-socket system, or on an AMD with cores in different CCX clusters). You'd like to benefit from per-core private caches (L1d and L2 in many modern CPUs.) So you'd more likely want to align your boundaries to cache-block boundaries. Or page boundaries (e.g. 4k) for TLB locality.
IIRC, Intel's L1d hardware prefetcher does work better for increasing address (looping "forward").
For memory bandwidth after starting, looping forwards and backwards is probably not harmful on modern x86 CPUs at least: Intel's L2 streamer HW prefetcher can track one forward and one backward stream per 4K page; see a quote from Intel's optimization manual.
It might even help memory-level parallelism to be crossing a 4K boundary in one part but not the other (where HW prefetch stops because contiguous virtual addresses might not be contiguous in physical address space). So one HW prefetch stream can still be working and keeping the memory pipeline fully utilized. (But we're parallelizing, and multiple cores can already saturate DRAM controllers, or with L3 hits, probably the interconnect between cores.) Out-of-order exec usually sees far enough ahead to get demand loads in flight from across the 4K boundary. The limiting factor in per-core memory bandwidth is usually latency and the number of outstanding requests one core can track, or DRAM bandwidth if you miss in last-level cache for huge arrays.
Thread creation
Normally you don't need to parallelize the thread-starting part, you just loop in the main thread until you've started all the workers. If that's significant compared to the actual work being done, use fewer threads (set a minimum chunk size) and/or have a pool of worker threads to reduce overhead of assigning work to them for jobs other than the first.
Maybe on an architecture that's significantly different from modern mainstream CPUs, where vastly more cores are available and it's cheaper to create threads. (But you still have to do so one at a time, unlike a GPU where things naturally run in parallel.)
Starting threads as you recurse probably makes it harder in practice to keep track of them for when you want to .join() them to make sure they've finished, or send them notifications or signals.
If you were going to do any rounding of the number of tasks or whatever, you might round the chunk size to a multiple of the page size so each thread makes the most use of its dTLB coverage. Or maybe work in somewhat smaller chunks like OpenMP "dynamic" scheduling so differences in CPU speed or scheduling don't leave one thread with a lot of work to do while the others are done. (Normally that's most useful for problems where the amount of work per chunk is actually variable, not just because of competing with other load on the system. n/k chunk size is what OpenMP calls "static" scheduling, where all the work is handed out to worker threads right away.)
Cancelling after one thread finds a match:
CPUs and OSes can do this easily and efficiently, it's just a question of whether the necessary tools are exposed in the high-level language you're using. It's often the case that the CPU being able to do something efficiently doesn't mean it's easy to write a portable program that does it efficiently, but I think we're ok in modern C++ for this.
One way is to have each thread check a shared atomic flag (like C++ std::atomic<bool> with memory_order_relaxed) every 1K or 4K bytes. It will normally stay hot in the L1d cache of all cores, invalidated (MESI) only when it's written by the thread that found the match. If the search speed is limited by cache or memory bandwidth, that won't slow us down. (Modern x86 can search faster than L2 cache bandwidth, if you use SIMD effectively like AVX2 to check 32 bytes at once, and aggregate some results to branch maybe every 64 or 128 bytes, like glibc memchr does. Or an example with intrinsics of searching for either of two bytes at odd positions.)
Or ask the OS to interrupt or kill the other threads, like via C++20 std::jthread which has a request_stop, or POSIX pthread_cancel with async cancellation enabled. (Or pthread_kill to send SIG_USR1 or something and exit the thread in the signal handler, or go to sleep to wait for the next batch of work if you're starting a pool of worker threads instead of creating/destroying OS-level threads for every parallel operation.) This has literally no overhead during the actual search work.
