Unit 8: Array Applications

1. Introduction to Array Applications
2. Searching Techniques
3. Sorting Techniques
4. Character Arrays
5. Exam Focus Enhancements

1. Introduction to Array Applications

Arrays are not just for storing data; they are the foundation for several fundamental algorithms in computer science. In this unit, we explore how to organize and retrieve data efficiently using Searching and Sorting algorithms, and how to handle text using Character Arrays.

2. Searching Techniques

Searching is the process of finding the location of a specific element (target) within an array. The two most common methods are Linear Search and Binary Search.

Linear Search

This is the simplest searching technique. It involves checking each element of the array one by one until the target is found or the end of the array is reached.

Best Case: Target is at the first position.
Worst Case: Target is at the last position or not present.
Applicability: Can be used on both sorted and unsorted arrays.

Binary Search

Binary search is a highly efficient algorithm, but it requires the array to be sorted beforehand. It works by repeatedly dividing the search interval in half.

Step 1: Compare the target with the middle element.
Step 2: If equal, the search is successful.
Step 3: If the target is smaller, repeat the search in the left half.
Step 4: If the target is larger, repeat the search in the right half.

3. Sorting Techniques

Sorting is the process of arranging the elements of an array in a specific order (ascending or descending).

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

How it works: In each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array.

// Pseudo-code for Bubble Sort
For i = 0 to n-2
    For j = 0 to n-i-2
        If array[j] > array[j+1]
            Swap(array[j], array[j+1])

4. Character Arrays

In C, a string is simply a one-dimensional character array that is terminated by a null character (\0).

Declaration and Initialization

char name[10]; // Declaration
char city[] = "Delhi"; // Initialization with null terminator automatically added
char greeting[] = {'H', 'e', 'l', 'l', 'o', '\0'}; // Manual initialization

Difference between Integer and Character Arrays

Feature	Integer Array	Character Array (String)
Termination	No special terminator.	Ends with a null character (\0).
I/O Functions	scanf("%d"), printf("%d").	scanf("%s"), gets(), puts().
Space Handling	Spaces are treated as delimiters.	gets() can read strings with spaces.

5. Exam Focus Enhancements

Exam Tips

Binary Search Condition: Always state that the array must be sorted for Binary Search to work. This is a common 2-mark question.
Null Terminator: When calculating the size of a character array for a string, always add +1 for the '\0' character.
Efficiency: If asked to compare search methods, mention that Binary Search is faster for large datasets, while Linear Search is better for small or unsorted ones.

Common Mistakes

Off-by-one Error: In loops for sorting or searching, ensure you don't go past the last index (N-1).
Swapping Logic: Forgetting to use a temporary variable while swapping elements in a sorting algorithm.
String Input: Using scanf("%s", str) to read a full name. This will only capture the first word. Use gets(str) or fgets() instead.

Frequently Asked Questions

Q: What is the significance of the null character (\0) in character arrays?
A: It acts as a marker to tell the compiler and functions (like printf) where the string ends.

Q: Why is Bubble Sort called "Bubble"?
A: Because smaller or larger elements "bubble" to the top/end of the list in each iteration.

Q: When should I use Linear Search over Binary Search?
A: When the array is small or when the data is not sorted and you don't want the extra overhead of sorting it first.