COMP 352 Lecture Notes - Lecture 22: Binary Search Algorithm, Enter Key, Time Complexity

• School: Concordia University
• Department: Computer Sci.
• Course: COMP 352
• Professor: T B A

Document Summary

Binary search implemented via sorted array or arraylist. Only search half of the input @ every step. Implemented via recursion, stop @ when key is found. If key is not in map then return null; else return old value associated with k. If map has an entry k, then it remove it otherwise return null. Returns size and whether if it is empty; respectively. Returns an iterable collection of entries in m. Similar actions to that of the put method. First (cid:455)ou (cid:374)eed to perfor(cid:373) get(cid:894)k(cid:895) to (cid:373)ake sure it value does(cid:374)"t alread(cid:455) e(cid:454)ist. Second, insert the key into the proper index in the array. Third, you need to shift the indices accordingly. Only key is important and shown in tree - value is not important. Left subtree has keys that are less than the root/parent. Right subtree has key that are greater than the root/parent. External nodes do not store items (they are null)