Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    Unit 3 Searching

    Uploaded by

    remojuly2005
    Ctc

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Unit 3 Searching

    Uploaded by

    remojuly2005
    2 views4 pages
    Ctc

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Ctc

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    2 views4 pages

    Unit 3 Searching

    Uploaded by

    remojuly2005
    Ctc

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 4

    There are two types of searching -

    o Linear Search
    o Binary Search
    Both techniques are widely used to search an element in the given list.
    What is a Linear Search?
    Linear search is a method of finding elements within a list. It is also called a sequential
    search. It is the simplest searching algorithm because it searches the desired element in a
    sequential manner.
    It compares each and every element with the value that we are searching for. If both are
    matched, the element is found, and the algorithm returns the key's index position.
    Concept of Linear Search
    Let's understand the following steps to find the element key = 7 in the given list.
    Step - 1: Start the search from the first element and Check key = 7 with each element of list
    x.

    Step - 2: If element is found, return the index position of the key.

    Step - 3: If element is not found, return element is not present.

    Linear Search Algorithm


    There is list of n elements and key value to be searched.
    Below is the linear search algorithm.
    LinearSearch(list, key)
    for each item in the list
    if item == value
    return its index position
    return -1
    Explanation:
    In the above code, we have created a function linear_Search(), which takes three arguments
    - list1, length of the list, and number to search. We defined for loop and iterate each element
    and compare to the key value. If element is found, return the index else return -1 which
    means element is not present in the list.
    Linear Search Complexity
    Time complexity of linear search algorithm -
    o Base Case - O(1)
    o Average Case - O(n)
    o Worst Case -O(n)

    Concept of Binary Search


    In the binary search algorithm, we can find the element position using the following
    methods.

    o Recursive Method
    o Iterative Method

    The divide and conquer approach technique is followed by the recursive method. In
    this method, a function is called itself again and again until it found an element in
    the list.

    A set of statements is repeated multiple times to find an element's index position in


    the iterative method. The while loop is used for accomplish this task.

    Binary search is more effective than the linear search because we don't need to
    search each list index. The list must be sorted to achieve the binary search algorithm.

    Let's have a step by step implementation of binary search.

    We have a sorted list of elements, and we are looking for the index position of 45.

    [12, 24, 32, 39, 45, 50, 54]

    So, we are setting two pointers in our list. One pointer is used to denote the smaller
    value called low and the second pointer is used to denote the highest value
    called high.

    Next, we calculate the value of the middle element in the array.


    1. mid = (low+high)/2
    2. Here, the low is 0 and the high is 7.
    3. mid = (0+7)/2
    4. mid = 3 (Integer)

    Now, we will compare the searched element to the mid index value. In this case, 32 is
    not equal to 45. So we need to do further comparison to find the element.

    If the number we are searching equal to the mid. Then return mid otherwise move to
    the further comparison.

    The number to be search is greater than the middle number, we compare the n with
    the middle element of the elements on the right side of mid and set low to low =
    mid + 1.

    Otherwise, compare the n with the middle element of the elements on the left side
    of mid and set high to high = mid - 1.

    Repeat until the number that we are searching for is found.


    def binary_search(list1, n):
    low = 0
    high = len(list1) - 1
    mid = 0

    while low <= high:


    # for get integer result
    mid = (high + low) // 2

    # Check if n is present at mid


    if list1[mid] < n:
    low = mid + 1

    # If n is greater, compare to the right of mid


    elif list1[mid] > n:
    high = mid - 1

    # If n is smaller, compared to the left of mid


    else:
    return mid

    # element was not present in the list, return -1


    return -1

    You might also like