3 searching algorithms in Java

3 searching algorithms in Java

• 1.
  using Java 2015 Data Structure Preparedby: Mahmoud Rafeek Al-farra in Java 3. Searching Algorithms
• 2.
  mfarra.cst.ps www.fb.com/MahmoudRFarra Contents Which isbest ? Binary Search approach Linear search approach Introduction
• 3.
  Introduction mfarra.cst.ps www.fb.com/MahmoudRFarra  Searchingfor data 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 (linear) search approach. The binary search approuach.
• 4.
  Linear search approach mfarra.cst.pswww.fb.com/MahmoudRFarra The linear search approach compares the key element sequentially with each element in the data structure.  It continues to do so until the key matches an element in the DS or the DS is exhausted without a match being found. If a match is made, the linear search returns the index of the element in the DS that matches the key.  If no match is found, the search returns -1.
• 5.
  Linear search approach mfarra.cst.pswww.fb.com/MahmoudRFarra 2 5 81 88 90 997 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 You can see an animated example from the following link: http://www.cs.armstrong.edu/liang/animation/web/LinearSearch.html
• 6.
  Linear search approach mfarra.cst.pswww.fb.com/MahmoudRFarra 1. public class LinearSearch { 2. /** The method for finding a key in the list */ 3. public static int linearSearch(int[] list, int key) { 4. for (int i = 0; i < list.length; i++) { 5. if (key == list[i]) 6. return i; 7. } 8. return -1; 9. } 10. }
• 7.
  Binary search approach mfarra.cst.pswww.fb.com/MahmoudRFarra 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. You can see an animated example from the following link: http://www.cs.armstrong.edu/liang/animation/web/BinarySearch.html
• 8.
  Binary Search approach mfarra.cst.pswww.fb.com/MahmoudRFarra
• 9.
  Binary Search approach 25 81 88 90 997 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 mfarra.cst.ps www.fb.com/MahmoudRFarra
• 10.
  Binary Search approach 25 81 88 90 997 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 mfarra.cst.ps www.fb.com/MahmoudRFarra
• 11.
  Binary Search approach mfarra.cst.pswww.fb.com/MahmoudRFarra 1. public class BinarySearch { 2. public static int binarySearch(int[] list, int key) { 3. int low = 0; 4. int high = list.length - 1; 5. while (high >= low) { 6. int mid = (low + high) / 2; 7. if (key < list[mid]) 8. high = mid - 1; 9. else if (key == list[mid]) 10. return mid; 11. else 12. low = mid + 1; 13. } 14. return –low - 1; // Now high < low, key not found 15. } 16. }
• 12.
  Which is best? mfarra.cst.ps www.fb.com/MahmoudRFarra The best Complexity Data structure Suitable data Size of data
• 13.
  Which is best? mfarra.cst.ps www.fb.com/MahmoudRFarra  If an array is sorted, binary search is more efficient than linear search for finding an element in the array.  Linear search is useful for finding an element in a small array or an unsorted array, but it is inefficient for large arrays.  Binary search is more efficient, but it requires that the array be presorted.
• 14.
  Which is best? mfarra.cst.ps www.fb.com/MahmoudRFarra Complexity time of linear approach is: O(n) Complexity time of binary approach is: O( log(n))  Supported data structure of linear: ?  Supported data structure of Binary: ?
• 15.
  using Java 2015 FB: Ma h m o u d R F a r r a YouTube: M a h m o u d R F a r SlidesShare: mralfarra Thank you