Unit 8: Array Applications
Contents
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
- 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.
- 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. Usegets(str)orfgets()instead.
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.