Linear Search Algorithm for Arrays

This content covers the implementation of the linear search algorithm for searching elements in arrays using various methods like for loops, while loops, and do-while loops. It explains the step-by-step process of searching for a target element in an array and provides code examples for better understanding.

• Arrays
• Searching
• Sorting
• Linear Search Algorithm
• Code Examples

vineyard_o Follow

Uploaded on Feb 22, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. ARRAYS - SEARCHING - SORTING

2. 1. LINEAR SEARCH Given: The array The search target: the array element value we are looking for Algorithm: Start with the initial array element (subscript 0) Repeat until there are more array elements (subscript = array size 1) Compare the target with the current element Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 2 2

3. 2. LINEAR SEARCH ILLUSTRATED gpa[0]= = target? gpa [0] gpa [1] gpa [2] gpa [30] gpa [31] gpa [48] gpa [49] 4.52 3.02 2.25 3.45 2.99 4.32 4.82 gpa[1]= = target? gpa[2]= = target? gpa[30]= = target? gpa[31]= = target? gpa[48]= = target? gpa[49]= = target? Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 3 3

4. 3. LINEAR SEARCH USING FOR - CODE The loop ends when the counter reaches the end of the array #include <stdio.h> int main (void) { double target, gpa[50]; int i; int index; int found = 0; // array initialization for (i = 0; i < 50; i++) { printf ( Enter element value> ); scanf ( %f , &gpa[i]); } // end for // Get the search target printf ( Enter the value you are looking for> ); scanf ( %f , &target); // Compare all array elements with the target for (i = 0; i < 50; i++) if (gpa[i] == target) { index = i; //store the position found = 1; // set flag to 1 } // end if if (found) // if (found == 1) printf ( Target %f is found at position %d \n , target, index); else printf ( Target not found ); return 0; } // end main // position of the found element // flag initially set to 0 Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 4 4

5. 4. LINEAR SEARCH USING WHILE Why going through the whole array if the target is found? It is better to update the code fragment in the previous slide as follows: int i = 0; int found = 0; while ((!found) && (i < 50)) { if (gpa[i] == target) break; else i++; } // end while int i = 0; int found = 0; while ((!found) && (i < 50)) { if (gpa[i] == target) found = 1; else i++; } // end while Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 5 5

6. 5. LINEAR SEARCH USING DOWHILE Since we need to perform the comparison at least once (with gpa[0]), then linear search can also be implemented using do while. The core code is as follows: int i = 0; int found = 0; do { if (gpa[i] == target) break; else i++; } while ((!found) && (i < 50)) int i = 0; int found = 0; do { if (gpa[i] == target) found = 1; else i++; } while ((!found) && (i < 50)) Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 6 6

7. 6. SWAPPING If you want to swap (exchange) the values of two variables, you need a third variable. For example, assume the following: x = 5 y = 8 To swap the values of x and y, we will use a temporary variable temp as follows: temp = x; x = y; y=temp; //temp=5 x=8 y=5 //temp=5 x=5 y=8 //temp=5 x=8 y=8 Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 7 7

8. 7. FINDING MINIMUM ELEMENT Assume the first element is the minimum value Go through all the array and find if there is a lesser value If there is a lesser value put it in minimum int i; int array_size; int minimum; minimum = x[0]; // assume x[0] is the minimum value in the array for (i = 0; i < array_size; i++) if (x[i] < minimum) minimum = x[i]; // counter // size of the array // to hold the minimum value of the array Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 8 8

9. 8. FINDING MINIMUM ELEMENT - TRACING int i, array_size, minimum; minimum = x[0]; for (i = 0; i < array_size; i++) if (x[i] < minimum) minimum = x[i]; x[0] 74 x[1] 45 x[2] 83 x[3] 16 array_size = 4 minimum x[0] = 74: initial value i++ 0: initial value 1 i < array_size? x[i] < minimum? 1 < 4? True x[1] < minimum? 45 < 74? True X[2] < minimum? 83 < 45? False X[3] < minimum? 16 < 45? True 45 2 2 < 4? True 45 3 3 < 4? True 16 4 4 < 4? False Exit from loop Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 9 9

10. 9. SORTING ARRAYS Sorting an arrays in ascending order is to arrange it such that: X[0] < x[1] < x[2] < x[3] < .. Example: Assume that we have the following array x[0] 74 x[1] 45 x[2] 83 x[3] 16 After being sorted the array will be as follows: x[0] 16 x[1] 45 x[2] 74 x[3] 83 Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 10 10

11. 10. SORTING ARRAYS ALGORITHM Let current position = 0 Find the minimum element in the array Swap with the current position Move to the next current position (current++) Repeat the same steps until you reach the end of the array Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 11 11

12. 11. SORTING ARRAYS ILLUSTRATED 1st iteration x[0] 74 x[1] 45 x[2] 83 x[3] 16 current = 0 Minimum element in the array x[0] to x[3] = 16 index_min = 3 (subscript) Swap x[current] with x[index_min] 2nd iteration x[0] 16 x[1] 45 x[2] 83 x[3] 74 current = 1 Minimum element in the array x[1] to x[3] = 45 index_min = current No swap needed Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 12 12

13. 11. SORTING ARRAYS ILLUSTRATED (CNTD) 3rd iteration x[0] 16 x[1] 45 x[2] 83 x[3] 74 current = 2 Minimum element in the array x[2] to x[3] = 74 index_min = 3 (subscript) Swap x[current] with x[index_min] 4th iteration x[0] 16 x[1] 45 x[2] 74 x[3] 83 current = 3 Minimum element in the array x[3] to x[3] = 83 index_min = current No swap needed The last iteration is not needed since only one element is left Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 13 13

14. 12. SORTING ARRAYS CODE #include <stdio.h> int main (void) { // declaration part int x[4], i, current, minimum, index_min, temp; // initialize the array for (i = 0; i < 4; i++) { printf ( enter x[%d] , i); // displayed as enter x[0] in the 1st iteration scanf ( %d , &x[i]); } // end for i for (current = 0; current < 3; current++) { // find minimum elementin the subarray starting from current // store the subscript of the minimum element (index_min) // if (current != index_min) swap } // end for current } //end main Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 14 14

15. 12. SORTING ARRAYS CODE (CNTD) for (current = 0; current < 2; current++) // limit = array_size - 2 { minimum = x[current]; // assume x[current] is the minimum index_min = current; // hold the corresponding subscript // find the minimum value in the sub-array starting from x[current] for (i = current; i < 3; i++) { if (x[i] < minimum) { minimum = x[i]; index_min = i; // store the subscript of the minimum element } // end if (x[i] < minimum) } // end for(i = current; // swap if index_min != current else do nothing if (index_min != current) { temp = x[index_min]; x[index_min] = x[current]; x[current] = temp; } // end if (index_min != current) } // end for (current = 0; } //end main Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 15 15

16. 13. SELF-CHECK EXERCISES Write a complete program to take two numerical lists of the same length 20. Then, the program stores the lists in arrays x and y; each of which is of length 20. Then, the program should do the following: Store the product of corresponding elements of x and y in a third array, z, also of size 20. Display the arrays x, y, z in a three-column table. Compute and display the square root of the sum of the items in z. Update the above program so that to use a sentinel value to end data entry. The arrays x, y and z are of length 5. Make up your own data and trace your program in the following cases: - The user entered exactly 5 numbers in each list - The user entered 6 numbers in each list - The user entered 3 numbers in each list Make necessary changes to your program accordingly. Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 16 16

17. 13. SELF-CHECK EXERCISES Write a complete program that performs the following to an array x of type int and length 20: - Fill the array with 20 values - Finds and displays the largest value in the array - Finds and displays the subscript of the largest value in the array Write an interactive program that stores a word in an array of characters. The program asks the user to guess a letter. The program should then check if this letter is in word or not. An appropriate message is displayed accordingly. The program ends after 3 times of incorrect guesses or when the user enters a sentinel value. Dr. Soha S. Zaghloul Dr. Soha S. Zaghloul 17 17