Lecture Data Structures: Lesson 39

Lecture Data Structures: Lesson 39 provide students with knowledge about searching an array: binary search; binary search – C++ code; binary search efficiency; overcome basic limitations of previous lists; fast searching of sorted chain; skip list representation; . | Searching an Array Binary Search Binary search is like looking up a phone number or a word in the dictionary Start in middle of book If name you re looking for comes before names on page look in first half Otherwise look in second half Lecture Data Structure Dr. Sohail Aslam Binary Search If value middle element value is found else if value lt middle element search left-half of list with the same method else search right-half of list with the same method Binary Search Case 1 val a mid val 10 low 0 high 8 mid 0 8 2 4 a 1 5 7 9 10 13 17 19 27 0 1 2 3 4 5 6 7 8 low mid high Binary Search - Example 2 Case 2 val gt a mid val 19 low 0 high 8 mid 0 8 2 4 new low mid 1 5 a 1 5 7 9 10 13 17 19 27 0 1 2 3 4 5 6 7 8 low mid new high low Binary Search - Example 3 Case 3 val lt a mid val 7 low 0 high 8 mid 0 8 2 4 new high mid-1 3 a 1 5 7 9 10 13 17 19 27 0 1 2 3 4 5 6 7 8 low new mid high high Binary Search - Example 3 cont val 7 a 1 5 7 9 10 13 17 19 27 0 1 2 3 4 5 6 7 8 a 1 5 7 9 10 13 17 19 27 0 1 2 3 4 5 6 7 8 a 1 5 7 9 10 13 17 19 27 0 1 2 3 4 5 6 7 8 Binary Search C Code int isPresent int arr int val int N int low 0 int high N - 1 int mid while low Binary Search binary tree An entire sorted list First half Second half First half Second half First half The search divides a list into two small sub- lists till a sub-list is no more divisible. Binary Search Efficiency After 1 bisection N 2 items After 2 bisections N 4 N 22 items . . . After i bisections N 2i 1 item i log2 N Implementation 3 linked list TableNodes are again stored consecutively unsorted or sorted key entry insert add to front 1or n for a sorted list find search through potentially all the keys one at a time n for unsorted or for a sorted list remove find remove using and so on pointer alterations n Implementation 4 Skip List Overcome basic limitations of previous lists Search and update require linear time Fast Searching of Sorted Chain Provide alternative to BST binary search trees and related tree .