عرض عملي: سباق بين البحث الخطي والبحث الثنائي

Written Explanation

Step 1: build a sorted array

We fill the array with even numbers, a[i] = i * 2. It is sorted by construction, and every odd number is guaranteed to be missing, so searching for 1 forces both algorithms to do the maximum work for the size.

int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = i * 2;

At 10,000,000 elements the array holds 40 million bytes of numbers (4 bytes per int), about 40 MB. That is fine for a normal laptop with the default Java settings, but if your machine reports an OutOfMemoryError, use 1,000,000 instead and say so in your results.

Step 2: time the search

System.nanoTime() returns a time in nanoseconds (billionths of a second). Its documentation says it can only be used to measure elapsed time: the starting point is arbitrary, so a single reading means nothing, but the difference between two readings from the same program does. It also warns that precision is not the same as resolution: values may change less often than every nanosecond, and the resolution is at least as good as currentTimeMillis(). So tiny durations are only rough.

long t0 = System.nanoTime();
int r1 = linearSearch(a, 1);
long t1 = System.nanoTime();
int r2 = binarySearch(a, 1);
long t2 = System.nanoTime();
System.out.println(n + " | " + (t1 - t0) + " | " + (t2 - t1));

We store the results r1 and r2 and later use them, for example by printing, so that the work is not quietly skipped. Both searches use the methods from the earlier lessons without counters.

Step 3: repeat, warm up, and read with care

The first run of Java code is often slower, because the Java runtime has not yet optimised it. Run the same measurement several times and look at the later runs. For the demo we also run both methods thousands of times on a small array before the real test (a "warm-up"). That is an informal technique, not a rigorous benchmark.

Results on one Windows machine with JDK 21 (your numbers will differ in size, and between runs):

Reading the table with care:

• n = 1,000. Both are tiny, around a microsecond (a thousand nanoseconds), and the numbers jump around. Binary search's first run at 47,800 ns is an outlier, more than forty times its later runs: this is the sort of one-off delay that makes a single timing misleading. At this size, timing cannot separate the two.
• n = 100,000. Linear search needs about 24,000 ns, binary about 1,500 ns. The gap is now clear.
• n = 10,000,000. Linear search needs about 4 million ns (4 ms), binary search about 6,000 ns. Binary search is hundreds of times faster here.

Step 4: explain the trend

Linear search grows with the data: 100 times more elements (1,000 to 100,000) made it roughly 20 to 50 times slower in this run, and another 100 times (to 10,000,000) made it about 170 times slower. It does not grow exactly in proportion because very small timings are noisy and because memory behaviour changes with array size, but the direction is clear and matches the count: 1,000 versus 100,000 versus 10,000,000 comparisons.

Binary search barely changes. Halving predicts at most about 10 looks at 1,000, about 17 at 100,000, and about 24 at 10,000,000 (the 1,000 case was counted earlier; the other two come from halving). Its times change by a small factor while the data grows ten thousand times. That agreement between the counts and the timings is the point of doing both.

A good written explanation says: (1) what was measured, (2) the table, (3) the trend (linear grows with n, binary almost flat), (4) a link to the step counts, and (5) a note about the limits (noise, one machine, one kind of target).

Step 5: the planned mistake

Now break it on purpose:

int[] u = {40, 10, 30, 20, 50, 60, 5};
System.out.println("unsorted: " + binarySearch(u, 5));
int[] s = u.clone();
Arrays.sort(s);
System.out.println(Arrays.toString(s) + " -> " + binarySearch(s, 5));

Output:

unsorted: -1
[5, 10, 20, 30, 40, 50, 60] -> 0

The value 5 is in the array, at index 6, but binary search on the unsorted array reports -1. The looks are: mid = 3 holds 20, larger than 5, so everything from index 3 on is discarded (including the 5 at index 6); mid = 1 holds 10, larger than 5, so the right side is discarded again; mid = 0 holds 40, larger than 5, and the range is empty. The search never looked at the end, where the 5 was hiding. After Arrays.sort, the same call finds 5 at index 0.

The lesson is that there is no error message. The program runs, prints a plausible answer, and is wrong. A search that returns "not found" for a value that exists is much more dangerous than one that crashes.