Introduction to Arrays

Arrays are one of the most commonly used datastructure. An Array stores the elements in a continous manner in the memory. The elements of an array can be either homogeneous i.e.., of same data type or heterogeneous i.e.., of different data types. Every programming language has it’s own way of implementation.

Typically, Arrays are categorized into two categories based on whether they have a fixed length.

1. Static Arrays : These arrays will have a fixed length.
2. Dynamic Arrays : These arrays will have variable length. The size can be increased as and when the need arises.

Defining an Array :

Python does not have static arrays. However, Dynamic Arrays have been implemented with the name list datatype.

list1 = [1,3,5,7,9]

Index position starts with the 0 and ends with n-1, if the list contains n elements.

Accessing elements of the Array :

One can access the elements of the array using the index position of the elements.

print(list1[0]) # prints 1st element of the list
print(list1[2]) # prints third element of the list

Time complexity for accessing element of an array using the index position is O(1).

Searching for a value in the Array :

The elements of the array can be in a sorted manner or in an unsorted manner. There are two ways of searching the values in the Array.

1. Linear Search Method :

Linear Search Method is mostly used when the elements of the array are not in sorted manner. We start from the 0th Index position to last element one by one and compare the value with the number to be searched.

list1 = [1,3,5,7,9]
num1 = int(input("Enter a number to be searched"))
bool1 = True
for i in range(0,len(list1)):
  if list1[i] == num1 :
    print("Number had been found at ",i)
    bool1 = False
if bool1 : 
  print("element not found in the list")
  

Time complexity of this algorithm is

2. Binary Search Method :

If the elements of the array are in sorted manner, then this is one of the optimal way for sorting them.

Get Alok Dubey’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Algorithm for Binary Search:

1. Identify the mid term of the array and compare it with the search value.
2. compare the mid term of the array with that of the search value. If it matches, then return.
3. If the mid term of the array is smaller than the search value, then the array will be midval+1 to end of array by ignoring the left side of the array. proceed to step 1.
4. if the mid term of the array is greater than the search value, the restrict the values to starting position of the array to midval-1 and discard the right side of the array. proceed to step1.

Binary Search can be impemented in two ways. First one is though iteration only and second one is through recursion.

The Binary Search Algorithm with the iterative method had been shown below.

def binary_search(list1,num1):
    lnum = 0
    rnum = len(list1)

    while rnum >= lnum:
        midval = int((rnum + lnum) / 2)
        if list1[midval] == num1:
            print(f'number found at {midval} using', {lambda n=0: sys._getframe(n + 1).f_code.co_name})
            bool1 = True
            return 0
        elif list1[midval] > num1:
            rnum = midval - 1
        elif list1[midval] < num1:
            lnum = midval + 1
    print('number not found using', {lambda n=0: sys._getframe(n + 1).f_code.co_name})
    return -1

Binary Search Method using the recursion had been displayed below.

def binary_search_rec(list1,num1,lnum,rnum):
    midval = int(lnum+rnum/2)
    if len(list1) <= 0 :
        return -1
    elif num1 == list1[midval]:
        print('found the value')
        return midval
    elif num1 < list1[midval]:
        return binary_search_rec(list1,num1,lnum,midval+1)
    elif num1 > list1[midval]:
        return binary_search_rec(list1,num1,midval+1,rnum)

Time complexity of this algorithm is O(log n).

Time complexity of insertion of elements :

If a new element is added to an existing array and if the memory adjacent to array had been occupied by any other data, then a new space will be allocated with a new size (say Original size of array + 2*Original size of array). The entire data needs to be copied to the new memory address as well.

The time complexity of inserttion if element is O(n).

Time complexity of deletion of elements :

If any element of an array is deleted, then all the elements next to it needs to be moved. Hence, the time complexity of deletion is O(n). However, if we are going to delete the last element of the array, the the time complexity is O(1).

Time complexity of traversal of elements :

The time complexity of traversal of elements is O(n), if there are n elements in the array.

Time complexity of display of an element of an array with the index :

The time complexity in this case is O(1). Since, all the elements are stored in continuos memory locations, the time taken to display any element using the index will be same.

Cons of the Arrays :

Arrays are an efficient means, if we need to read them. If we need to perform the constant operations of updation, then they will incur a lot of cost. The Arrays needs continuous memory for storing the elements. It may be difficult to allocated the continuous memory in some of the scenarios. In those situations, the linked list will come handy.

The entire code can be found here.

Would you like to know about the linked list ? Then go ahead and read from here.

If you have any queries or the feedback, please let me know in comments section.

Isn’t it fascinating to implement our own class for defining an array and it’s methods ? This post will enthuse you.