24. Searching and Complexity

  • Before continuing, we should take a moment and reflect on what we have learned so far

    • The Python programming environment is a relatively familiar sight (Colab, IPython, PyCharm, Spyder)

    • You know how to print and input information

    • You know about types, values, and variables

    • You have been making use of functions

    • You have learned about basic logic and know how to use if and else

    • for and while loops are tools you have used

    • You learned how to use objects

    • Linear data structures, like a List, are familiar and you are used to working with reference variables

    • You know how to read and write data from/to files

    • You have learned how to write classes and define your own objects

    • You can look at Python code and have a reasonable understanding of what it is doing

    • You know how to write your own code, one step at a time

    • You know the importance of testing your code and how to write tests

  • The last few topics of the course have been heavy on data and data structures

  • At this stage of the course, we have actually equipped ourselves with the majority of tools programmers use on a daily basis

  • Here, we will start to focus more on algorithms and how we can use all the tools we have learned to solve more interesting problems

  • Further, we will take some time to think about the amount of work the algorithm does and what makes an algorithm good

24.3. Linear Search in Other Programming Languages

  • At this stage we have been programming exclusively in Python

  • However, there are many other programming languages

  • Learning a new programming language may feel intimidating, but you may be surprised at how similar many of them are

    • First, the underlying algorithms are the same, regardless of the language — a linear search is a linear search

    • Second, even the syntax between many languages are remarkably similar

  • Below is a collection of linear search algorithms in various popular programming languages

    • The purpose of their inclusion here is to get a sense of how similar and dissimilar programing languages can be

  • Despite never learning the various languages, chances are you can still understand much of the code completely

24.3.1. Python

1def linear_search(haystack: list[int], needle: int) -> bool:
2    for i in range(len(haystack)):
3        if haystack[i] == needle:
4            return True
5    return False

24.3.2. Java

1public static boolean linearSearch(int[] haystack, int needle){
2    for(int i = 0 ; i < haystack.length ; i++){
3        if(haystack[i] == needle){
4            return true;
5        }
6    }
7    return false;
8}

24.3.3. C#

1public static boolean linearSearch(int[] haystack, int needle){
2    for(int i = 0 ; i < haystack.length ; i++){
3        if(haystack[i] == needle){
4            return true;
5        }
6    }
7    return false;
8}

24.3.4. C++

1bool linear_search(std::vector<int> haystack,  int needle){
2    for(int i = 0 ; i < haystack.size() ; i++){
3        if(haystack[i] == needle){
4            return true;
5        }
6    }
7    return false;
8}

24.3.5. C

1bool linear_search(int haystack[], int n, int needle){
2    for(int i = 0 ; i < n ; i++){
3        if(haystack[i] == needle){
4            return true;
5        }
6    }
7    return false;
8}

24.3.6. Haskell

  • Below you will see a linear search that looks quite different from the previous

  • Haskell is an entirely different kind of programming language — it is a functional programming language

    • It is, for better or worse, not nearly as popular as the languages seen in the above examples

1linear_search :: Eq a => [a] -> a -> Bool
2linear_search [] _ = False
3linear_search (x:xs) y = x==y || linear_search xs y

24.4. For Next Class