Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • Hashing : 55

    • Binary Search : 54

    • Quicksort : 53

    • Merge Sort : 52

    • Sorting Algorithms : 51

    • Practice with Recursion : 50

    • Trees and Recursion : 49

    • Trees : 48

    • Recursion : 47

    • Lists Review and Performance : 46

    • Linked Lists : 45

    • Algorithms and Lists : 44

    • Lambda Expressions : 43

    • Anonymous Classes : 42

    • Practice with Interfaces : 41

    • Implementing Interfaces : 40

    • Using Interfaces : 39

    • Working with Exceptions : 38

    • Throwing Exceptions : 37

    • Catching Exceptions : 36

    • References and Polymorphism : 35

    • References : 34

    • Data Modeling 2 : 33

    • Equality and Object Copying : 32

    • Polymorphism : 31

    • Inheritance : 30

    • Data Modeling 1 : 29

    • Companion Objects : 28

    • Encapsulation : 27

    • Constructors : 26

    • Objects, Continued : 25

    • Introduction to Objects : 24

    • Compilation and Immutability : 23

    • Practice with Collections : 22

    • Maps and Sets : 21

    • Lists and Type Parameters : 20

    • Imports and Libraries : 19

    • Multidimensional Arrays : 18

    • Practice with Strings : 17

    • null : 16

    • Algorithms and Strings : 15

    • Strings : 14

    • Functions and Algorithms : 13

    • Practice with Functions : 12

    • More About Functions : 11

    • Errors and Debugging : 10

    • Functions : 9

    • Practice with Loops and Algorithms : 8

    • Algorithms I : 7

    • Loops : 6

    • Arrays : 5

    • Compound Conditionals : 4

    • Conditional Expressions and Statements : 3

    • Operations on Variables : 2

    • Variables and Types : 1

    • Hello, world! : 0

    Binary Search

    fun search(values: IntArray, lookingFor: Int): Boolean {
    return false
    }
    assert search(arrayOf(1, 2, 4), 4)

    This lesson covers one of the efficient algorithms enabled by sorting: binary search! This is a fun example of an algorithm that you can approach either recursively or iteratively. We’ll walk through it visually and then let you tackle it on the homework problem.

    Binary Search
    Binary Search

    One of the reasons that sorting is such an important algorithmic primitive is that it enables other efficiency algorithms. For example, we’ve already seen linear array search, which has runtime O(n):

    fun search(values: IntArray, lookingFor: Int): Boolean {
    for (value in values) {
    if (value == lookingFor) {
    return true
    }
    }
    return false
    }
    assert search(new int[]{1, 2, 4}, 4);

    Given that O(n) represents searching the entire array, it is clearly the worst case runtime for array search. But, it is also the best case if we have no idea where the item could be!

    But what if we knew something about the structure of the data in the array. Specifically, what if we knew that it was sorted? Could we do better?

    Or, as my old graduate school friend David Malan famously explained it:

    Binary Search Runtime
    Binary Search Runtime

    Binary search is one recursive algorithm where the O(log n) nature of the algorithm is fairly easy to understand. Start with an array of N items. After one round, you have N / 2 left to consider. Then N / 4. Then N / 8. Until you either get to 1, or you find the item somewhere along the way. So in the worst case we do O(log n) steps, and in the best case we may do better. Cool!

    Search Visualizations
    Search Visualizations

    As promised, a few cool search visualizations culled from the amazing interwebs. This one has sound!

    These are also pretty good, as they show runtime for different inputs as well.

    Implementing Binary Search
    Implementing Binary Search

    Now it’s your chance to implement this classic algorithm! There are good approaches that use both recursion and iteration. The iterative approach maintains the start and end index of where the item might be in the array and adjusts these on each iteration. The recursive approach has the base case being an empty or single-item array, and makes the problem smaller by determining whether the item should be in the left half-array or right half-array. Good luck and have fun!

    Homework: BinarySearcher Array (int)

    Created By: Geoffrey Challen
    / Version: 2021.4.0

    Let's implement a classic algorithm: binary search on an array.

    Implement method named search that takes a SearchList as its first parameter and an Int as its second. If the SearchList is empty you should throw an IllegalArgumentException.

    SearchList is a provided class. It provides a get(Int) method that returns the Int at that index, and a size method that returns the size of the SearchList. Those are the only two methods you should need! You can also access the list elements using bracket notation just like a list or array: list[position].

    search returns a Boolean indicating whether the passed value is located in the sorted SearchList. To search the sorted SearchList efficiently, implement the following algorithm:

    • Examine the value in the middle of the current array (index (start + end) / 2)
    • If the midpoint value is the value that we are looking for, return true
    • If the value that we are looking for is greater than the midpoint value, adjust the current array to start at the midpoint
    • if the value that we are looking for is less than the midpoint value, adjust the current array to end at the midpoint
    • Continue until you find the value, or until the start reaches the end, at which point you can give up and return false

    This is a fun problem! Good luck! Keep in mind that every time you call SearchList.get or use bracket notation that counts as one access, so you'll need to reduce unnecessary accesses to pass the test suite. Specifically, you should only call list.get once per iteration, saving the result into a temporary variable.

    More Practice

    Need more practice? Head over to the practice page.