Linear Search and Binary Search with Tracing (ICSE Class 10 Java)

Understand Linear Search and Binary Search Tracing

int pos = -1;
for (int i = 0; i < a.length; i++)
    if (a[i] == key) { pos = i; break; }

int low = 0, high = a.length - 1, pos = -1;
while (low <= high) {
    int mid = (low + high) / 2;
    if (a[mid] == key) { pos = mid; break; }
    else if (a[mid] < key) low = mid + 1;
    else high = mid - 1;
}

Linear Search and Binary Search Tracing: key facts

Linear search

• •Check from index 0
• •Stop when a[i] equals key
• •Found at index k: k + 1 comparisons
• •Absent: n comparisons

Works on any array.

Binary search

• •Array must be sorted
• •mid = (low + high) / 2
• •Key smaller: high = mid - 1
• •Key larger: low = mid + 1
• •Stop when low is greater than high

Integer division for mid.

Maximum steps of binary search

n = 7	3
n = 15	4
n = 1000	about 10

Maximum steps = floor(log2 n) + 1. For example, n = 8 needs at most 4 steps, since log2 8 = 3.

Not found marker

• •pos = -1 at the start
• •Set pos = index when found
• •pos still -1 means not found

A common convention in programs.

How to answer Linear Search and Binary Search Tracing questions

1. 1Write the array with its indices; for binary search check that it is sorted.
2. 2Linear: move i from 0, compare a[i] with the key at each step, stop at the first match or at the end.
3. 3Binary: set low = 0, high = n - 1, then compute mid = (low + high) / 2 using integer division.
4. 4Compare a[mid] with the key; move low to mid + 1 or high to mid - 1; recompute mid.
5. 5Stop when found or when low is greater than high; count the steps.

Linear Search and Binary Search Tracing in real life

The idea, met in an everyday situation. Answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Tricks to remember Linear Search and Binary Search Tracing

Short memory aids. Say each one aloud once, then use it on a question the same day.

• Low-High-Mid

  Write low, high and mid in three columns and fill a row per step.

  Use it when: Binary search traces.

• Smaller means go left

  If the key is smaller than a[mid], high = mid - 1; if larger, low = mid + 1.

  Use it when: Direction of the search.

• Sorted first

  No sorting, no binary search.

  Use it when: Choosing a method.

Linear Search and Binary Search Tracing: solved examples

Ordered from board level to HOTS. Try each one before you open the solution.

int[] a = {7, 3, 9, 3, 5};
int key = 3, first = -1, count = 0;
for (int i = 0; i < a.length; i++)
    if (a[i] == key) {
        count++;
        if (first == -1) first = i;
    }
System.out.println(first + " " + count);

int[] a = {3, 8, 12, 19, 25, 31, 40};
int key = 25, low = 0, high = a.length - 1, pos = -1;
while (low <= high) {
    int mid = (low + high) / 2;
    System.out.print(mid + " ");
    if (a[mid] == key) { pos = mid; break; }
    else if (a[mid] < key) low = mid + 1;
    else high = mid - 1;
}
System.out.println(pos);

Where students lose marks in Linear Search and Binary Search Tracing

The slips examiners see most often, and what to write instead.

• ✗Mistake: Applying binary search to an unsorted array

  The decision to discard half the array is only valid when the data is in order.

  Wrong working

  Binary search on {9, 2, 7, 4}

  Right working

  Sort first, then search; or use linear search

  ✓Do this: Check the order first.

  Usually costs: 1 to 2 marks

• ✗Mistake: Using mid instead of mid + 1 or mid - 1

  The element at mid has already been checked; low = mid can loop for ever.

  Wrong working

  low = mid;

  Right working

  low = mid + 1;

  ✓Do this: Always move past mid.

  Usually costs: 1 mark

• ✗Mistake: Writing the loop condition as low < high

  When one element is left, low equals high and it must still be checked.

  Wrong working

  while (low < high)

  Right working

  while (low <= high)

  ✓Do this: Use <=.

  Usually costs: 1 mark

Practice questions on Linear Search and Binary Search Tracing

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · MCQBoard level

   Binary search can be applied to an array only if the array is:
   (a) of integers only (b) sorted (c) of size less than 10 (d) two-dimensional

   Hint

   Why can half of the array be discarded?

   Answer

   (b) sorted

2. Q2 · 1 mark · Very short answerBoard level

   Write the formula used to find the middle index in binary search.

   Hint

   Uses low and high.

   Answer

   mid = (low + high) / 2

3. Q3 · 2 marks · Short answerHarder board level

   Write the output of the binary search program of the worked example with key 8 on {3, 8, 12, 19, 25, 31, 40}.

   Hint

   First mid is 3.

   Answer

   3 1 1 (mid 3: 19 > 8 so high = 2; mid 1: 8 found, pos = 1)

4. Q4 · 3 marks · Short answerHarder board level

   Write a static method int find(int[] a, int k) that returns the index of the first occurrence of k using linear search, or -1 if absent. What are find(new int[]{4, 9, 2}, 2) and find(new int[]{4, 9, 2}, 7)?

   Hint

   Return inside the loop.

   Answer

   static int find(int[] a, int k) {
   for (int i = 0; i < a.length; i++)
   if (a[i] == k) return i;
   return -1;
   }
   find for key 2 returns 2; for key 7 returns -1.

5. Q5 · 1 mark · Assertion-reasonHOTS / competency

   Assertion (A): Binary search is faster than linear search on a large sorted array.
   Reason (R): Each step of binary search halves the portion of the array that remains to be searched.
   (a) Both A and R are true and R is the correct explanation of A. (b) Both A and R are true but R is not the correct explanation of A. (c) A is true but R is false. (d) A is false but R is true.

   Hint

   Compare the number of steps.

   Answer

   (a) Both are true and R explains A.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.What does binary search require?Show answer

   A sorted array.

2. 2.What is mid for low = 0 and high = 6?Show answer

   3

3. 3.How many comparisons does linear search need if the key is at index 4?Show answer

   5

4. 4.When does binary search stop with not found?Show answer

   When low becomes greater than high.

5. 5.If key is smaller than a[mid], which pointer moves?Show answer

   high = mid - 1.

6. 6.Which search works on unsorted data?Show answer

   Linear search.

Linear Search and Binary Search Tracing: frequently asked questions