Algorithms - Searching Part 1

Sequential Search

The elements stored in a array or list have a linear relationship with respect to each other. The linear relationship is the index values associated with each element. Since this relationship is ordered , we can visit the elements in a sequence and search through them.

A sequential search involves traversing the array element by element and searching each element being traversed. If the element is found while traversing we return the index/True. If we traverse the entire array and the element cannot be found we return a -1/False.

Case 1: Un-ordered array data, The elements appearing in the list do not align ascending order i.e unsorted data. codepad = http://codepad.org/zMtQrZnL

#Sequential search
#Author Thejas
def sequentialSearch(inputList , searchElement):
    found = False
    i = 0 #we start searching from index 0
    inputListLength = len(inputList)

    while i < inputListLength and not found:
        if inputList[i] == searchElement:
            found = True
        else:
            i = i + 1

    return found

def main():
    inList = [2,3,4,1,8,5,6,9,17,12,11,10]
    print sequentialSearch(inList, 11)
    print sequentialSearch(inList, 111)


if __name__ == '__main__':

    main()

Output:

1 2	True False

Time Complexity:

The best case performance in a sequential search is when the element is in the 0th index of the array i.e 1 comparison. The worst case performance of the sequential search is when the element is in the last index (1 less than the length of array ) i.e n comparisons.

o(1) and O(n)

Case 2: Ascending Ordered data: