Create FREE 'HowTo' Videos with MyGuide


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”

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

  • 5






  • 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 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.