Create FREE 'HowTo' Videos with MyGuide

Searching



Pass Quiz and Get a Badge of Learning



Content "filtered", Please subscribe for FULL access.


Chapter 10 : Searching


Searching Algorithms arrow_upward


  • Searching Algorithms are closely related to the concept of dictionaries.
  • Dictionaries are data structures that support:
    • Search operations
    • Insert operations
    • Delete operations
  • A search algorithm is for finding an item with specified properties among a collection of items.
  • The items may be stored individually as records in a database. 

  • Uses of Searching Algorithms arrow_upward


  • Finding a particular piece of data in a data structure.
  • Example:
    • Find the student who is named “Tom” from an array of students.

    Types of Searching Algorithms arrow_upward


  • Sequential Search
  • Binary Search
  • Breadth First Search
  • Depth First Search

  • Sequential Search arrow_upward


  • A sequential search of a list begins at the beginning of the list and continues until the item is searched.
  • This is a method for finding a particular value in a list that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.

  • Example of a Searching Algorithm arrow_upward


    Unordered-Linear-Search [A, n, x]:
    for i ← 1 to n
    do if A[i] = x
    then return i
    else i ← i + 1
    return “x not found”
    

    Ordered-Linear-Search [A, n, x]:
    for i ← 1 to n
    do if A[i] = x
    then return i
    else if A[i] < x
    then i ← i + 1
    else return “x not found”
    return “x not found”
    
    Example:

  • Search for an element 2 in the list below using sequential search.

  • 5

    20

    9

    4

    2

    18


  • Solution:
    • Search element is 2.

    • Search element 2 is found.

    Binary Search arrow_upward


  • Binary search looks for an item in a list using a divide and conquer strategy.

  • Binary Search Rules arrow_upward


  • The binary search algorithm assumes that the items in the array being searched are sorted.
  • The algorithm begins at the middle of the array in a binary search.
  • If the item for which we are searching is less than the middle, then it must reside in the top half of the array.
  • The search stops when the value has been found (or when it has been shown that the value does not appear on the list).
  • At each stage, half of the remaining list is discarded.

  • Algorithm for Binary Search arrow_upward


    Step 1

  • The algorithm compares the search value with the middle value in the list.
  • Either

  • The search value is found to be at this position.
  • Or

  • The search value occurs before the middle of the list.
  • Or

  • The search value occurs after the middle of the list.
  • Step 2

  • If (a) occurs, the search is over.
  • If (b) occurs, the search continues with Step 1 on a reduced list.
  • Consisting of those values before the middle value.
  • If (c) occurs, the search continues with Step 1 on a reduced list.
  • Consisting of those values   after the middle value.

  • Example:
    • Perform a binary search for 8 in a given array (6 8 12 20 22).
  • Given a value and sorted array a [ ], find the index  such that .
  • Step 1:
  • Step 2:
    • The middle value is 12, so the search value 8 occurs before 12.
  • Step 3:
  • Step 4:
  • Step 5:
    • Middle value is 8 which is the required search value.
  • Step 6:
    • Search terminates.

    Thank You from Kimavi arrow_upward


  • Please email us at Admin@Kimavi.com and help us improve this tutorial.


  • Mark as Complete => Receive a Certificate in Data-Structure


    Kimavi Logo

    Terms and conditions, privacy and cookie policy | Facebook | YouTube | TheCodex.Me | Email Kimavi


    Kimavi - A Video Learning Library { Learning is Earning }

    Get Ad Free Learning with Progress Report, Tutor Help, and Certificate of Learning for only $10 a month



    All videos on this site created using MyGuide.

    Create FREE HowTo videos with MyGuide.