logo

Snefru: Learning Programming with C

  • Snefru: Learning Programming with C

Preface

  • What about programming?
  • Principles of using this textbook

Book Chapters

  • 1. Introduction to Programming Computers
    • 1.1. The Basic Structure of Computers
    • 1.2. Binary representation in memory
    • 1.3. Development Cycle
    • 1.4. Write Simple C Programs
  • 2. Data representation and operations
    • 2.1. Double data type for real numbers
    • 2.2. Data types and representation
    • 2.3. Operations
    • 2.4. Math library
    • 2.5. Random numbers
    • 2.6. Exercises
  • 3. Decision-Making Statements
    • 3.1. If-statements
    • 3.2. Multiple Conditions
    • 3.3. Nested-if statements
    • 3.4. Exercises
  • 4. Repetition
    • 4.1. While Loop
    • 4.2. Do-while loop
    • 4.3. For loops
    • 4.4. Nested loops
    • 4.5. Debugging for loops
    • 4.6. Exercises
  • 5. Functions
    • 5.1. Functions
    • 5.2. Communicate from a function
    • 5.3. Variable scope
    • 5.4. Pass more values to a function
    • 5.5. Exercises
  • 6. Pointers
    • 6.1. Why do we need pointers?
    • 6.2. What are pointers?
    • 6.3. How to use pointers to communicate more with functions?
    • 6.4. Rules defining scope of variables
    • 6.5. Goldbach conjecture
    • 6.6. Exercises
  • 7. Arrays
    • 7.1. Why and how to use arrays?
    • 7.2. What are arrays, and how are they stored?
    • 7.3. How do we pass an array to a function?
    • 7.4. Exercises
  • 8. Dynamic Memory Allocation
    • 8.1. What is dynamic memory allocation?
    • 8.2. Exercises
  • 9. Multi-dimensional Arrays
    • 9.1. Why and how to use 2D arrays?
    • 9.2. How do we pass a 2D array to a function?
    • 9.3. Dynamic Memory Allocation of 2D Arrays
    • 9.4. Exercises
  • 10. Strings
    • 10.1. What are strings?
    • 10.2. Input/Output Strings
    • 10.3. String Functions
    • 10.4. Array of Strings
    • 10.5. Exercises
  • 11. Recursion
    • 11.1. Recursive functions by definition
    • 11.2. Recursion in Patterns
    • 11.3. Recursion in arrays
    • 11.4. Exercises
  • 12. Data Structures
    • 12.1. What are data structures?
    • 12.2. Pointers to Data Structures
    • 12.3. Exercises
  • 13. Linked Lists
    • 13.1. Why linked lists?
    • 13.2. Form a linked list
    • 13.3. Insert nodes into a linked list
    • 13.4. Delete nodes in a linked list
    • 13.5. Exercises
  • 14. Sorting
    • 14.1. Insertion Sort
    • 14.2. Selection Sort
    • 14.3. Bubble sort
    • 14.4. Exercises
  • 15. Searching
    • 15.1. Linear/Sequential Search
    • 15.2. Binary Search
    • 15.3. Exercises

Appendix: Additional information

  • Appendix: Additional Resources
  • Set up Visual Studio Code
  • More Extensions in VS Code
  • Coding style
  • Debugging
  • Basic UNIX Commands
Powered by Jupyter Book
  • repository
  • open issue
  • .md

Linear/Sequential Search

15.1. Linear/Sequential Search#

Linear search is a very simple search algorithm. It is called linear search because it searches the list in a linear fashion, checking each element in sequence until the desired element is found or until all the elements have been searched and the desired element was not found.

We discuss the algorithm on arrays, but it applies to any data structure. For example, the algorithm can be used to search a linked list.

The algorithm for linear search is as follows:

  1. Start at index = 0

  2. Check if list[index] == desired element in variable item

  3. If found, return index

  4. Otherwise, increment index by 1

  5. Repeat steps \(2\) – \(4\) until index is equal to the length of the list (or the element is found)

The algorithm is implemented in the following code snippet:

Code

1int sequentialSearch(int list[], int listLength, int item) {
2  for (int index = 0; index < listLength; index++) {
3    if (item == list[index]) {
4      return index;
5    }
6  }
7  return -1;
8}

If item is found, the algorithm returns the index of the element in the list in line \(4\). If item is not found, the algorithm returns -1 in line \(7\).

In the following example, we look for the element 7 in the array. Download the following code sequential-search.c if you want to play with it.

Code


#include <stdio.h>

int sequentialSearch(int list[], int listLength, int item) { for (int index = 0; index < listLength; index++) { if (item == list[index]) { return index; } } return -1; }
int main(void) { int list[] = {3, 5, 6, 7, 9}; printf("Found 7 at index %d.\n", sequentialSearch(list, 5, 7)); return 0; }

The minimum number of comparisons to find the desired element is 1, and the maximum number of comparisons is the length of the list. The average number of comparisons is \(\frac{n}{2}\), where \(n\) is the length of the list.

This would mean if I have 1000 elements in my list, the worst case scenario would be 1000 comparisons. If I have 10000 elements in my list, the worst case scenario would be 10000 comparisons. This is not very efficient. Is there a more efficient way to search for a desired element? Yes, there is. We will discuss this in the next section.

Quiz

0 Questions

X

previous

15. Searching

next

15.2. Binary Search

By Salma Emara et al.
© Copyright 2022–2025.