Chapter 4: basic search algorithms data structure

Chapter 4: basic search algorithms data structure

• 1.
  DATA STRUCTURE Chapter 4:Basic Search Algorithms Prepared & Presented by Mr. Mahmoud R. Alfarra 2010-2011 College of Science & Technology Dep. Of Computer Science & IT BCs of Information Technology http://mfarra.cst.ps
• 2.
  Out Line  Introduction Sequential Search Algorithm  Binary Search Algorithm  Which is the best ?  Search and sorting in Array List 2
• 3.
  Introduction  Searching fordata is a fundamental computer programming task and one that has been studied for many years.  There are two fundamental ways to search for data in a list: the sequential search and the binary search. 3
• 4.
  Sequential Search Algorithm 4  Themost obvious type of search is to begin at the beginning of a set of records and move through each record until you find the record you are looking for or you come to the end of the records. This is called a sequential search.  A sequential search (also called a linear search) is very easy to implement.
• 5.
  Sequential Search Algorithm 5 2 581 88 90 99 7 9 34 55 56 66 79 80 1 2 3 4 5 6 7 8 9 10 11 12 13 Wanted = 80 array 0 == ‫؟‬ .... .... The wanted value at comparison number 10 and position 9
• 6.
  Sequential Search Algorithm 6 1.static void Main(string[] args) 2. { int[] a = { 10, 2, 34, 4, 3, 1, 100 }; 3. int wanted = 1; 4. int target_index=-1; 5. for (int i = 0; i < a.Length; i++) 6. if (a[i] == wanted) { 7. target_index = i; 8. break; } 9. if (target_index >= 0) 10. Console.WriteLine(" The wanted value exist at position: "+(target_index+1)+"'th"); 11. Console.Read(); } Practice: Reprogram this problem using string data.
• 7.
  Binary Search Algorithm 7 When the records you are searching through are sorted into order, you can perform a more efficient search than the sequential search to find a value. This search is called a binary search.  To use this algorithm, we first need our data stored in order (ascending, preferably) in an array.
• 8.
  Binary Search Algorithm 8
• 9.
  Binary Search Algorithm 9 25 81 88 90 99 7 9 34 55 56 66 79 80 1 2 3 4 5 6 7 8 9 10 11 12 13 (0+13) / 2 = 6 If (array[6] == 80) return 6 Elseif (array[6] > 80) High = 6 -1 Else Low = 6+1 Middle = (low + high)/2 Wanted = 80 array 0 (7+13) / 2 = 10 If (array[10] == 80) return 10 Elseif (array[10] > 80) High = 10 -1 Else Low = 10+1 (7+9) / 2 = 8 If (array[8] == 80) return 8 Elseif (array[8] > 80) High = 8-1 Else Low = 8+1 1 2 3
• 10.
  Binary Search Algorithm 10 25 81 88 90 99 7 9 34 55 56 66 79 80 1 2 3 4 5 6 7 8 9 10 11 12 13 Middle = (low + high)/2 Wanted = 80 array 0 (7+9) / 2 = 8 If (array[8] == 80) return 8 Elseif (array[8] > 80) High = 8-1 Else Low = 8+1 3 (9+9) / 2 = 9 If (array[9] == 80) return 8 Elseif (array[9] > 80) High = 9-1 Else Low = 9+1 4 return 8
• 11.
  Binary Search Algorithm 11 ‫البيانات‬‫تراكيب‬ ‫مساق‬ ‫إعداد‬ ‫العلمية‬ ‫المادة‬ / ‫أ‬ . ‫ا‬ َّ‫الفــر‬ ‫رفيق‬ ‫محمود‬ 1. static void Main(string[] args) { 2. int[] a = { 2, 3, 5, 8, 10, 23, 30}; 3. int wanted = 23; 4. int start = 0; 5. int last = a.Length - 1; 6. int middle = (last + start) / 2; 7. int result =0; 8. while (start < last) { 9. middle = (last + start) / 2; 10. if (a[middle] == wanted) { 11. result = 1; 12. break; } 13. else if (a[middle] < wanted) 14. start = middle + 1; 15. else 16. last = middle - 1; } 17. if (result == 1) 18. Console.WriteLine("The wanted element is exist at: " + middle); 19. else 20. Console.WriteLine("The wanted element does not exist "); To understand: trace step by step To practice: try with string data More practice: try with 2-D array
• 12.
  Which is thebest ? 12  Sequential search is used when the items in the list are in random order.  Binary search is used when the items are sorted in the list.
• 13.
  Search and sortingin Array List 13 1. static void Main(string[] args) { 2. ArrayList a = new ArrayList(); 3. a.Add(20); 4. a.Add(4); 5. a.Add(3); 6. a.Sort(); 7. int result = a.BinarySearch(3); 8. Console.WriteLine(" position of 3 at : " + result); 9. result = a.BinarySearch(7); 10. Console.WriteLine(" position of 7 at : " + result); 11. Console.WriteLine(); 12. foreach (object x in a) 13. Console.WriteLine(" " + x); 14. Console.ReadLine(); }
• 14.
  Thank You … 14 Rememberthat: question is the key of knowledge
• 15.
  Ahl Eljanna   َ‫ق‬َ ‫د‬َ ‫ص‬‫ي‬ّ ‫ذ‬‫ه‬‫ل‬‫ا‬ ّ‫ه‬ّ ‫َلِل‬ ُ ‫د‬‫ح‬ ‫م‬َ‫ح‬ ‫ْل‬‫ا‬ ‫وا‬ُ‫ل‬‫ا‬َ‫ق‬َ ‫و‬ ‫ا‬ ‫ا‬َ‫ن‬َ‫ث‬َ ‫ر‬‫ح‬ ‫َو‬‫أ‬َ ‫و‬ ُ‫ه‬َ ‫د‬‫ح‬‫ع‬َ ‫و‬ ‫ا‬َ‫ن‬ ُ‫أ‬‫ه‬ ‫و‬َ‫ب‬َ‫ت‬َ‫ن‬ َ ‫ض‬‫ح‬ ‫ر‬َ‫ح‬ ‫ْل‬ َ ‫م‬‫ح‬‫ع‬ّ‫ن‬َ‫ف‬ ُ‫اء‬َ ‫ش‬َ‫ن‬ ُ ‫ث‬‫ح‬‫ي‬َ ‫ح‬ ّ ‫هة‬‫ن‬َ‫ح‬ ‫ْل‬‫ا‬ ‫ح‬ ‫ن‬ّ ‫م‬ َ ‫ي‬ّ‫ل‬ّ ‫ام‬َ ‫حع‬‫ل‬‫ا‬ ُ ‫ر‬‫ح‬ ‫َج‬‫أ‬ 15