Java Arrays: Searching, Sorting and 2D Arrays (ISC Class 11 Computer Science)

Understand Arrays in Java: One-dimensional Arrays, Searching, Sorting and 2D Arrays

int a[] = new int[5];          // five elements, indices 0 to 4
int b[] = {12, 45, 7, 33, 21}; // initialised

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] == key) return mid;
    else if (a[mid] < key) lo = mid + 1;
    else hi = mid - 1;
}

Arrays in Java: One-dimensional Arrays, Searching, Sorting and 2D Arrays: key facts

Array facts

• •Indices 0 to length - 1
• •length = number of elements
• •Out of range gives ArrayIndexOutOfBoundsException

Fixed size.

Bubble sort count

Passes = n - 1 | Comparisons = (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2

Without a flag.

Binary search

• •mid = (low + high)/2
• •Halve the range each time
• •Needs a sorted array

About log2 n steps.

How to answer Arrays in Java: One-dimensional Arrays, Searching, Sorting and 2D Arrays questions

1. 1Write the array and the loop variables.
2. 2For sorting, record the array after each pass.
3. 3For binary search, record low, high, mid and the element at mid.
4. 4Count comparisons or swaps if asked.

Arrays in Java: One-dimensional Arrays, Searching, Sorting and 2D Arrays 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 Arrays in Java: One-dimensional Arrays, Searching, Sorting and 2D Arrays

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

• Index starts at zero

  An array of n elements has indices 0 to n - 1.

  Use it when: Indexing.

• Bubble: big floats up

  The largest value goes to the end after the first pass.

  Use it when: Bubble sort.

• Binary needs sorted

  No sorted array, no binary search.

  Use it when: Search.

Arrays in Java: One-dimensional Arrays, Searching, Sorting and 2D Arrays: solved examples

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

int a[] = {12, 45, 7, 33, 21};
int max = a[0], min = a[0], sum = 0;
for (int i = 0; i < a.length; i++) {
    if (a[i] > max) max = a[i];
    if (a[i] < min) min = a[i];
    sum += a[i];
}
System.out.println(max + " " + min + " " + sum + " " + (double) sum / a.length);

Where students lose marks in Arrays in Java: One-dimensional Arrays, Searching, Sorting and 2D Arrays

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

• ✗Mistake: Using index n

  Counting from 1.

  Wrong working

  for (i = 0; i <= a.length; i++)

  Right working

  for (i = 0; i < a.length; i++)

  ✓Do this: Last index is length - 1.

  Usually costs: 1-2 marks.

• ✗Mistake: Binary search on an unsorted array

  Ignoring the condition.

  Wrong working

  Binary search on 7 3 5 1

  Right working

  Sort first

  ✓Do this: State the pre-condition.

  Usually costs: 2 marks.

• ✗Mistake: Integer division in the average

  118 / 5 gives 23.

  Wrong working

  sum / a.length = 23

  Right working

  (double) sum / a.length = 23.6

  ✓Do this: Cast before dividing.

  Usually costs: 1-2 marks.

Practice questions on Arrays in Java: One-dimensional Arrays, Searching, Sorting and 2D Arrays

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

   The index of the last element of an array of 10 elements is:
   (a) 9 (b) 10 (c) 11 (d) 0

   Hint

   Zero-based.

   Answer

   (a) 9

2. Q2 · 3 marks · Short answerBoard level

   Write a Java code segment to find and print the sum of the elements of the array int a[] = {4, 9, 2, 7}. State the output. (3 marks)

   Hint

   Accumulate in a loop.

   Answer

   int s = 0; for (int i = 0; i < a.length; i++) s += a[i]; System.out.println(s); Output: 22.

3. Q3 · 5 marks · Long answerHarder board level

   Trace the selection sort for 64, 25, 12, 22, 11 and write the array after each pass. Count the swaps. (5 marks)

   Hint

   Smallest to the front.

   Answer

   Pass 1: 11 25 12 22 64; pass 2: 11 12 25 22 64; pass 3: 11 12 22 25 64; pass 4: 11 12 22 25 64. Swaps (with a swap each pass) = 4, of which the last swaps an element with itself.

4. Q4 · 5 marks · Long answerHarder board level

   Given int m[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; write the output of a program that prints the row sums, the main diagonal sum and the other diagonal sum. (5 marks)

   Hint

   i == j and i + j == 2.

   Answer

   Row sums: 6, 15, 24. Main diagonal: 1 + 5 + 9 = 15. Other diagonal: 3 + 5 + 7 = 15.

5. Q5 · 3 marks · Short answerHOTS / competency

   A programmer wrote: int a[] = {5, 1, 4}; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (a[j] > a[j + 1]) swap. Find the error that occurs at run time, the first index at which it happens, and the correction. (3 marks)

   Hint

   j + 1 goes to 3.

   Answer

   When j = 2, a[j + 1] = a[3] is outside 0 to 2: ArrayIndexOutOfBoundsException. The inner loop must run to j < 2 (that is, j < n - 1 - i).

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.First index of an array?Show answer

   0.

2. 2.Binary search needs?Show answer

   A sorted array.

3. 3.Comparisons in bubble sort for n=5?Show answer

   10.

4. 4.Default value of int array?Show answer

   0.

5. 5.Passing an array to a method passes?Show answer

   A reference.

Arrays in Java: One-dimensional Arrays, Searching, Sorting and 2D Arrays: frequently asked questions