Searching Algorithm Linear Search In Array Simple Go through the Array till you find the item If end of the Array then item does not exist 2006 Goodrich Tamassia Linked Lists 1 Searching Algorithm Linear Search In List Simple Go through the Array till you find the key item If end of the Array then key does not exist 2006 Goodrich Tamassia Linked Lists 2 Searching Algorithm Binary search in Array Look for the key in the middle of the array If found return Else if key is or the item in middle Then look for the item in lower half of the array Else look for item in upper half of the array Do this in non recursive way 2006 Goodrich Tamassia Linked Lists 3 Searching Algorithm Binary search in Array Look for the key in the middle of the array If found return Else if key is or the item in middle Then look for the item in lower half of the array Else look for item in upper half of the array Do this in recursive way 2006 Goodrich Tamassia Linked Lists 4 Searching Algorithm Inserting an item in Sorted Array Make sure Array is not full Find the position where to insert Move all other items to make space for insertion What is the Big O if search is linear first search and then insert O n for search and insert What was the big O for insertion in array but unsorted Insert an item in sorted array search is done using bin search What is big O for inserting an item first search and then insert 2006 Goodrich Tamassia Linked Lists 5 Searching Algorithm Inserting an item in Sorted linked list Find position in linked list Insert item make links What is the Big O first search and then insert O logn for search and insert What was the big O for insertion in linked list but unsorted 2006 Goodrich Tamassia Linked Lists 6 int rBin search int sortedArray int first int last int key if first last int mid first last 2 compute mid point cout mid mid endl if key sortedArray mid return mid found it else if key sortedArray mid Call ourself for the lower part of the array return rBin search sortedArray first mid 1 key else Call ourself for the upper part of the array return rBin search sortedArray mid 1 last key return first 1 failed to find key 2006 Goodrich Tamassia Linked Lists 7 Searching Algorithm Binary search in linked list How 2006 Goodrich Tamassia Linked Lists 8
View Full Document
Unlocking...