-
Notifications
You must be signed in to change notification settings - Fork 0
/
readme.txt
79 lines (53 loc) · 3.1 KB
/
readme.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/******************************************************************************
* Name: Jaret Kadlec
*
* Hours to complete assignment (optional):
* 10
******************************************************************************/
Programming Assignment 2: Autocomplete
/******************************************************************************
* Describe how your firstIndexOf() method in BinarySearchDeluxe.java
* finds the first index of a key that equals the search key.
firstIndexOf searches for any key that equals the search key by using a simple
binary search algorithm (dividing the search area in half until found, return
-1 if not). Once it gets to that key, it iterates forward through the array until the
end of the array is found or other values are found to find the first index of the value.
*****************************************************************************/
/******************************************************************************
* What is the order of growth of the number of compares (in the
* worst case) that each of the operations in the Autocomplete
* data type make, as a function of the number of terms n and the
* number of matching terms m? (Big-Oh notation)
*
* Recall that with order-of-growth notation, you should discard
* leading coefficients and lower-order terms, e.g., m^2 + m log n.
*****************************************************************************/
constructor: O(logN)
allMatches(): O(NlogN)
numberOfMatches(): O(logN)
/******************************************************************************
* Known bugs / limitations.
No known bugs or limitations
*****************************************************************************/
/******************************************************************************
* Describe whatever help (if any) that you received.
* Don't include readings or lectures, but do include
* any help from people (including course staff, lab TAs,
* classmates, and friends) and attribute them by name.
*
* Also include any resources (including the web) that you may
* may have used in creating your design.
Explanation of binary search by khan academy: https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array
*****************************************************************************/
/******************************************************************************
* Describe any serious problems you encountered.
Creating the binary search was the most challenging part of this assignment,
but I was able to draw it out on paper and get a better understanding of how
to implement the search.
*****************************************************************************/
/******************************************************************************
* List any other comments here. Feel free to provide any feedback
* on how much you learned from doing the assignment, and whether
* you enjoyed doing it.
It was a fun assignment!
*****************************************************************************/