Problem 1 Linear Search with finding one occurrence

The problem

You are given an array and a target key. Return the index of one occurrence of key (any one is acceptable), or -1 if it is absent. The single-threaded answer is a textbook scan in O(n) time. The interesting version asks: can you use several threads to finish sooner on a large array?

The idea is data parallelism. Split the array into contiguous chunks, give one chunk to each thread, and let every thread scan its own chunk independently. The first thread to spot the key publishes its index into a single shared variable, guarded so two threads cannot trample each other. After all threads join, that shared variable holds the answer.

The shared state and why it needs a guard

Three pieces of state are shared across threads:

• foundIndex — a single integer, initialised to -1, where the winning thread writes the index it found.
• mtx — a lock (Java synchronized block / Go sync.Mutex) that serialises access to foundIndex.
• The array itself, which is read-only during the search, so it needs no guard.

The write to foundIndex is a read-modify-write: a thread must check whether the slot is still -1 before claiming it, so that the first finder wins and a later finder does not overwrite it. That check-then-set is exactly the kind of compound operation that breaks without a lock, so it lives inside the guarded region. The variable is also declared volatile so a thread that polls it sees writes made by other threads rather than a stale cached copy.

How the work is partitioned

With NUM_THREADS threads over an array of length n, each thread takes a contiguous block of size chunkSize = n / NUM_THREADS. Thread t scans [t·chunkSize, t·chunkSize + chunkSize), and the last thread also absorbs the remainder so no element is skipped.

The code below sets NUM_THREADS = 4. That number matters for the worked example: it is not two equal halves shared between two workers — it is four blocks. On a tiny six-element array the division is 6 / 4 = 1, so the first three threads each own exactly one element and the fourth thread mops up the final three. Keep that partition in mind; the trace later follows it exactly.

The early-exit poll, and its honest limitation

Inside its scan loop, each thread can stop early if some other thread has already found the key — there is no point finishing a chunk once the answer exists. But reading shared state on every iteration would mean taking the lock millions of times and would destroy the speed-up the parallelism was meant to deliver. So the code polls only occasionally, using a stride:

if ((i & 1023) == 0) {        // once every 1024 elements
  synchronized (mtx) {
    if (foundIndex != -1) break;
  }
}

This is a deliberate trade-off, and it is worth being honest about what it buys. The poll fires only when the low ten bits of i are zero — i.e. at indices 0, 1024, 2048, … So the early exit can only trigger help on chunks long enough to span a multiple of 1024. On a six-element array, no thread ever re-polls after its first index, and the early exit is effectively inert. Even on large arrays the saving is bounded: a thread may still scan up to ~1024 elements past the moment another thread found the answer before it next checks. The early exit is a coarse, best-effort optimisation that trims worst cases on big inputs; it is not a tight, immediate stop, and on small inputs it does essentially nothing. The correctness of the result never depends on it — the join at the end is what guarantees the answer.

Worked trace, step by step

Array [4, 15, 7, 3, 12, 9], key = 12, four threads, chunkSize = 1. The partition is t0→idx 0, t1→idx 1, t2→idx 2, t3→idx 3,4,5.

Notice what does not happen: no thread ever early-exits mid-chunk on this input, because no chunk re-reaches the 1024-stride. t3 scans idx 3 and idx 4 without ever re-reading found. The answer, 4, is established when main joins the threads and reads the shared variable.

Reference implementation

Java and Go, behaviourally identical: contiguous blocks, a lock-guarded check-then-set on a single foundIndex, and a coarse stride-1024 early-exit poll.

Java

public class Solution {
  private static final int NUM_THREADS = 4;
  private static final Object mtx = new Object();
  private static volatile int foundIndex = -1;

  private static void linearSearch(int threadId, int[] arr, int key) {
    int chunkSize = arr.length / NUM_THREADS;
    int start = threadId * chunkSize;
    int end = (threadId == NUM_THREADS - 1) ? arr.length : start + chunkSize;

    for (int i = start; i < end; ++i) {
      if ((i & 1023) == 0) {              // coarse early-exit poll
        synchronized (mtx) {
          if (foundIndex != -1) break;
        }
      }
      if (arr[i] == key) {
        synchronized (mtx) {
          if (foundIndex == -1) {
            foundIndex = i;
            break;
          }
        }
      }
    }
  }

  public static void main(String[] args) throws InterruptedException {
    int[] arr = {4, 15, 7, 3, 12, 9};
    int key = 12;
    Thread[] threads = new Thread[NUM_THREADS];
    for (int t = 0; t < NUM_THREADS; ++t) {
      final int id = t;
      threads[t] = new Thread(() -> linearSearch(id, arr, key));
      threads[t].start();
    }
    for (Thread th : threads) th.join();
    System.out.println(foundIndex == -1
        ? "Element not found in the array."
        : "Element found at index: " + foundIndex);
  }
}

Go

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
)

const numWorkers = 4

func main() {
	arr := []int{4, 15, 7, 3, 12, 9}
	key := 12
	var found int64 = -1 // -1 means not found

	chunk := len(arr) / numWorkers
	var wg sync.WaitGroup
	for t := 0; t < numWorkers; t++ {
		start := t * chunk
		end := start + chunk
		if t == numWorkers-1 {
			end = len(arr)
		}
		wg.Add(1)
		go func(start, end int) {
			defer wg.Done()
			for i := start; i < end; i++ {
				if i&1023 == 0 && atomic.LoadInt64(&found) != -1 {
					return // coarse early-exit poll
				}
				if arr[i] == key {
					atomic.CompareAndSwapInt64(&found, -1, int64(i))
					return
				}
			}
		}(start, end)
	}
	wg.Wait()

	if found == -1 {
		fmt.Println("Element not found in the array.")
	} else {
		fmt.Println("Element found at index:", found)
	}
}

The Go version uses an atomic CompareAndSwap instead of a mutex for the check-then-set: it atomically writes the index only if the slot is still -1, giving the same first-finder-wins semantics without an explicit lock.

Complexity

• Work: O(n). Parallelism does not reduce total comparisons; in the worst case every element is still examined.
• Span / wall-clock: roughly O(n / NUM_THREADS) when threads run on separate cores and the key is absent or late, since each scans about n / NUM_THREADS elements in parallel.
• Space: O(NUM_THREADS) for the threads plus O(1) shared state.

The parallel version only pays off when n is large enough that the scan dominates thread-creation and synchronisation overhead. On a six-element array, spawning four threads is far slower than a plain loop — the example exists to make the partition and the shared-state mechanics legible, not because it is the fast way to search six numbers.

Pitfalls

• Unguarded check-then-set. If two threads both find the key and write foundIndex without the lock (or without the == -1 guard), a later finder can overwrite an earlier one, or the read of -1 and the write can interleave. The lock plus the inner if (foundIndex == -1) is what makes first-finder-wins hold.
• Forgetting volatile / using a plain read. Without volatile (Java) or an atomic load (Go), a polling thread may keep reading a stale cached -1 and never observe another thread's write — the early-exit poll becomes not just coarse but blind.
• Over-trusting the early exit. The stride-1024 poll is a best-effort trim on large inputs, not a guarantee. If the contract is the lowest index of the key — rather than any occurrence — this design does not provide it: different threads can find equal keys in different blocks, and which write lands first is non-deterministic, so the returned index is merely some occurrence. Solve "first occurrence" by having each thread record its own local minimum and reducing to the global minimum after the join.
• Off-by-one in the remainder. When n is not divisible by NUM_THREADS, only the last thread's end must extend to arr.length. Splitting the remainder anywhere else silently skips or double-scans elements.

Source

Adapted from the Knowledge Guide concurrency track, “Problem 1 — Linear Search with finding one occurrence,” part of the Data Parallelism (Partition / Map / Reduce) pattern group. Trace, partition, and complexity figures verified against the NUM_THREADS = 4, stride-1024 reference implementation shown above.