CP164 Study Guide - Final Guide: Array Data Structure, Binary Search Algorithm, Linear Search
The Array-Based SortedList Implementation
The general notes about an array-based implementations for Lists also apply to a
SortedList.
The front of the SortedList, insomuch as it has one (which applies for the purposes of
searching) is the left-most inhabited element in the SortedList. The size of the SortedList at
any given time is simply the number of array elements that contain values, or right-most
element index + 1. No array elements can be left empty. A SortedList is empty if the array
element with index 0 is empty. The contents of a SortedList are kept in sorted order.
Implementing the Array-Based SortedList
The following code shows how to implement part of the array-based SortedList in Python.
The rest is left to you as an exercise for labs and assignments.
Initializing an Array-Based SortedList
See the initializations for a List.
Getting the Length of an Array-Based SortedList
... is identical to the List __len__ method.
Implementing the [] Operator
... is identical to the List __getitem__ operator, and requires the same improvements to its
definition to work correctly.
Implementing the _binary_search Method
The binary search method serves the SortedList in the same capacity as the linear search
serves the List. It is a helper method used by the re move andindex methods to find the
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
The general notes about an array-based implementations for lists also apply to a. The front of the sortedlist, insomuch as it has one (which applies for the purposes of searching) is the left-most inhabited element in the sortedlist. The size of the sortedlist at any given time is simply the number of array elements that contain values, or right-most element index + 1. A sortedlist is empty if the array element with index 0 is empty. The contents of a sortedlist are kept in sorted order. The following code shows how to implement part of the array-based sortedlist in python. The rest is left to you as an exercise for labs and assignments. Is identical to the list __len__ method. Is identical to the list __getitem__ operator, and requires the same improvements to its definition to work correctly. The binary search method serves the sortedlist in the same capacity as the linear search serves the list.
