Sequential & binary, linear search

Sequential & binary, linear search

1. WELCOMETO OUR PRESENTATION Daffodil International University

2. LINEAR BINARY SEARCH

3. What is searching? In computer science, searching is the process of finding an item with specified properties from a collection of items. The items may be stored as records in a database, simple data elements in arrays, text in files, nodes in trees, vertices and edges in graphs, or maybe be elements in other search place.

4. Why do we need searching? Searching is one of the core computer science algorithms. We know that today’s computers store a lot of information. To retrieve this information proficiently we need very efficient searching algorithms.

5. Binary Search Let us consider a problem of searching a word in a dictionary. Typically, we directly go to some approximate page[say, middle page] start searching from that point. If the name that we are searching is same then the search is complete. If the page is before the selected pages then apply the process for the first half otherwise apply the same process for the second half. Binary search also works in the same way. The algorithm applying such strategy is referred as binary search algorithm.

6. Sequential or Linear search

7. BINARY SEARCH 1 5 8 24 12 36 48 87 67 54 ENTER THE ARRAY ELEMENTS ENTER THE NUMBER TO BE SEARCHED 36 M[0] M[1] M[2] M[3] M[4] M[5] M[6] M{7] M[8] M[9]

8. BINARY SEARCH 1 5 8 24 12 36 48 87 67 54 ENTER THE NUMBER TO BE SEARCHED 36 M[0] M[1] M[2] M[3] M[4] M[5] M[6] M{7] M[8] M[9] LB UB

9. P=LB+UB/2 24 STEP 1 FIND THE MIDDLE ELEMENT P=0+9/2

10. 24 36 < 36 48 54 67 87 THE SEARCH ELEMENT LIES IN THE UB 1 2 3 4 COMPARING SEARCH WITH MIDDLE ELEMENT STEP 2

11. P=LB+UB/2 54 54 > 36 36 48 STEP 3 DIVIDE THE ARRAY FURTHER COMPARING SEARCH WITH MIDDLE ELEMENT THE SEARCH ELEMENT LIES IN THE LB

12. 36 36 = NUMBER FOUND STEP 4 36 48 MIDDLE ELEMENT IS COMPARED WITH THE ELEMENTS IN THE ARRAY

13. #include< stdio.h > int   main(){      int   a[10], i,n,m,c =0,l,u,mid;     printf ("Enter the size of an array: ");     scanf ("% d",&n );     printf ("Enter the elements in ascending order: ");      for(i=0;i< n;i ++){          scanf ("% d",&a [i]);     }     printf ("Enter the number to be search: ");     scanf ("% d",&m ); CODE

14.     l=0,u=n-1;      while(l<=u){          mid=( l+u )/2;           if(m==a[mid]){              c=1;               break;          }           else   if(m<a[mid]){              u=mid-1;          }           else              l=mid+1;     }      if(c==0)          printf ("The number is not found.");      else          printf ("The number is found.");      return   0; }

15. Enter the elements of the array in ascending order 12 Enter the elements of the array in ascending order 23 Enter the elements of the array in ascending order 34 Enter the elements of the array in ascending order 45 Enter the elements of the array in ascending order 56 Enter the elements of the array in ascending order 67 Enter the elements of the array in ascending order 78 Enter the elements of the array in ascending order 89 Enter the elements of the array in ascending order 98 Enter the elements of the array in ascending order 100 Enter the number to be searched 67 found

16. binary search Use/Application

17. LINEAR SEARCH 10 46 8 99 6 2 34 1 95 78 ENTER THE NUMBER TO BE SEARCHED 2 M[0] M[1] M[2] M[3] M[4] M[5] M[6] M{7] M[8] M[9]

18. LINEAR SEARCH 10 46 8 99 6 2 34 1 95 78 2 2 2 2 2 2 THE NUMBER IS FOUND IN THE 6 TH POSITION

19. #include < stdio.h >   int main() { int array[100], search, c, n;   printf ("Enter the number of elements in array \n "); scanf ("% d",&n );   printf ("Enter %d integer(s) \n ", n); for (c = 0; c < n; c++ ) scanf ("%d", &array[c]);   CODE

20.   printf("Enter the number to search \n "); scanf("%d", &search);   for (c = 0; c < n; c++) { if (array[c] == search) /* if required element found */ { printf("%d is present at location %d. \n ", search, c+1); break ; } } if (c == n) printf("%d is not present in array. \n ", search);   return 0; }

21. SUBMITTED TO : THANK YOU