Scribd Logo
Upload

Welcome to Scribd!

  • 50 views

    Linear Search

    Uploaded by

    Safal Bhattarai
    Linear search is a sequential search algorithm that starts at one end of a list and checks each element in turn until the target element is found or the end of the list is reached. It is the simplest search algorithm and can be performed on both sorted and unsorted lists or arrays. Binary search is a more efficient searching algorithm used to search sorted arrays by repeatedly dividing the search interval in half. It works by comparing the target value to the middle element of the array each time, eliminating half of the elements from further search.

    Copyright:

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

    Linear Search

    Uploaded by

    Safal Bhattarai
    50 views11 pages
    Linear search is a sequential search algorithm that starts at one end of a list and checks each element in turn until the target element is found or the end of the list is reached. It is the simplest search algorithm and can be performed on both sorted and unsorted lists or arrays. Binary search is a more efficient searching algorithm used to search sorted arrays by repeatedly dividing the search interval in half. It works by comparing the target value to the middle element of the array each time, eliminating half of the elements from further search.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Linear search is a sequential search algorithm that starts at one end of a list and checks each element in turn until the target element is found or the end of the list is reached. It is the simplest search algorithm and can be performed on both sorted and unsorted lists or arrays. Binary search is a more efficient searching algorithm used to search sorted arrays by repeatedly dividing the search interval in half. It works by comparing the target value to the middle element of the array each time, eliminating half of the elements from further search.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    50 views11 pages

    Linear Search

    Uploaded by

    Safal Bhattarai
    Linear search is a sequential search algorithm that starts at one end of a list and checks each element in turn until the target element is found or the end of the list is reached. It is the simplest search algorithm and can be performed on both sorted and unsorted lists or arrays. Binary search is a more efficient searching algorithm used to search sorted arrays by repeatedly dividing the search interval in half. It works by comparing the target value to the middle element of the array each time, eliminating half of the elements from further search.

    Copyright:

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

    LINEAR SEARCH

    Linear Search is defined as a sequential search algorithm that starts at one end and
    goes through each element of a list until the desired element is found, otherwise the
    search continues till the end of the data set.
    · Linear search is the simplest method for searching.
     In Linear search technique of searching; the element to be found in searching the
    elements to 
    be found is searched sequentially in the list.
     This method can be performed on a sorted or an unsorted list (usually arrays).
    ·  It is the most simple search algorithm in data structure and checks each item in the
    set of 
    elements until it matches the search element until the end of data collection.
     When data is unsorted, a linear search algorithm is preferred.
    ·  The linear search algorithm searches all elements in the array sequentially.
    searching algorithm
    Linear Search Algorithm

    Step 1: First, read the search element (Target element) in the array.
    Step 2: In the second step compare the search element with the first element in the array.
    Step 3: If both are matched, display “Target element is found” and terminate the Linear Search 
    function.
    Step 4: If both are not matched, compare the search element with the next element in the array.
    Step 5: In this step, repeat steps 3 and 4 until the search (Target) element is compared with the 
    last element of the array.
    Step 6 – If the last element in the list does not match, the Linear Search Function will be 
    terminated, and the message “Element is not found” will be displayed.
     
    Examples:

    •Input:  compare the value of every index with x if they match return index
    • Follow the given steps to solve the problem:
    •-Set the first element of the array as the current element.
    •-If the current element is the target element, return its index.
    •-If the current element is not the target element and if there are more elements in the array, set the current
    element to the next element and repeat step 2.
    •-If the current element is not the target element and there are no more elements in the array, return -1 to
    indicate that the element was not found.
    Coding:

    • 
    •def search (arr, N, x):
    •for i in range (0, N):
    • if (arr[i] == x):
    • return i
    • return -1
    • 
    •# Driver Code
    •if __name__ == "__main__":
    • arr = [2, 3, 4, 10, 40]
    • x = 10
    • N = len(arr)
    • 
    • # Function call
    • result = search(arr, N, x)
    • if(result == -1):
    • print("Element is not present in array")
    • else:
    • print("Element is present at index", result)
     
    Advantages of Linear Search:

    •-Linear search is simple to implement and easy to understand.


    •-Linear search can be used irrespective of whether the array is sorted or not. It can be used on arrays of any
    data type.
    •-Does not require any additional memory.
    •-It is a well-suited algorithm for small datasets.

    •DISADVANTAGES OF LINEAR SEARCH:

    •-Not suitable for large array.


    •-Linear search can be less efficient than other algorithms, such as hash tables.
    When to use Linear Search:

    •-When we are dealing with a small dataset.


    •-When you need to find an exact value.
    •-When you are searching a dataset stored in contiguous memory.
    •-When you want to implement a simple algorithm.

    •It is used for searching databases, lists, and arrays


    BINARY SEARCH
    • Binary Search is a searching algorithm used in a sorted array
    by repeatedly dividing the search interval in half. The idea of binary
    search is to use the information that the array is sorted. 
    Binary Search Algorithm: 
    • The basic steps to perform Binary Search are:
    • Sort the array in ascending order.
    • Set the low index to the first element of the array and the high index to the last element.
    • Set the middle index to the average of the low and high indices.
    • If the element at the middle index is the target element, return the middle index.
    • If the target element is less than the element at the middle index, set the high index to
    the middle index – 1.
    • If the target element is greater than the element at the middle index, set the low index
    to the middle index + 1.
    • Repeat steps 3-6 until the element is found or it is clear that the element is not present
    in the array.
    Iterative Binary Search

    • In the case of Iterative algorithms, a certain set of statements are repeated a certain number of time.An Iterative
    algorithm will use looping statements such as for loop, while loop or do-while loop to repeat the same steps
    number of time.

    • The main() method of Iterative BinarySearch class starts off with defining a Array of size 6, named A.
    • Key is the number to be searched in the list of elements.
    • Inside the while loop, "mid" is obtained by calculating (low+high)/2.
    • If number at position mid equal to key or target element then the control returns index of mid element by printing that the
    number has been found along with the index at which it was found.
    *Else, if key or target is less than number at position mid then the portion of the Array from the mid upwards is removed
    from contention by making "high" equal to mid-1.
    • Else, it implies that key element is greater than number at position mid(as it is not less than and also not equal, hence, it has
    to be greater). Hence, the portion of the list from mid and downwards is removed from contention by making "low" equal
    to mid+1.
    • The while loop continues to iterate in this way till either the element is returned (indicating key has been found in the Array)
    or low becomes greater than high,in which case -1 is returned indicating that key could not be found and the same is printed
    as output.
    Recursive Binary Search

    • Recursive algorithm, a function calls itself again and again till the base condition(stopping
    condition) is satisfied.
    • Recursive implementation of binary search algorithm, in the method binary Search(), follows
    almost the same logic as iterative version, except for a couple of differences.
    • The first difference is that the while loop is replaced by a recursive call back to the same method
    with the new values of low and high passed to the next recursive invocation along with "Array"
    and "key" or target element.
    • The second difference is that instead of returning false when the while loop exits in the iterative
    version, in case of the recursive version, the condition of low > high is checked at the beginning of
    the next level of recursion and acts as the boundary condition for stopping further recursive calls
    by returning false.
    • Also, note that the recursive invocations of binary Search() return back the search result up the
    recursive call stack so that true or false return value is passed back up the call stack without
    any further processing.

    You might also like