Array: Linear Search


Arrays:

Arrays are a sequential collection of similar datatypes. They are stored in memory at adjacent memory locations.

Arrays are like neighbouring houses, each house has a Plot number or House number known as index in case of arrays. Each house has people who live in it similar to that the array has data at each memory location.

In the above example 0, 1, .., 4 are indexes and 1000.0, 2.0, ..., 50.0 are data values stored on those indexes.
# define an array 
arr = [1, 2, 7, 4, 5, 8, 0]

# print values of the array
# C for loop equivalent for array of length n => for(int i = 0; i < n; i++) 
for i in range(len(arr)):
     print(arr[i], end=' ')

# Output: 1 2 7 4 5 8 0
Arrays are generally used to store multiple values of similar datatype. Rather than defining 100 variable with 100 different names to store values we can define an array of size 100 and access each value by their array index.

Array Searching:

Searching an element in an array is a common use case and it can be done in many ways depending on the arrangement of elements in array.

Linear Search:

The linear search is a simple looking out at all the values in the array comparing each value (val) with the key (x) we want to search.

Algorithm:

# Given an array 'arr' and a key 'x' to be searched
for i from 0 to length(arr)-1:
   if arr[i] == x:
     return i 
   end if
end for
return -1

Code in Python 3:

Note: In python indentation is used to define scope or block of code. 

# Function for linear search
# inputs: array of elements 'arr', key to be searched 'x'
# returns: index of first occurrence of x in arr 
def linear_search(arr, x):

  # traverse the array
  for i in range(0, len(arr)):
    
    # if element at current index is same as x
    # return the index value
    if arr[i] == x:
      return i
      
  # if the element is not found in the array return -1
  return -1

Example:



Let the input array be: [1, 2, 6, 10, 13, 20, 25, 26, 27, 30] 
and x = 20.

1. i = 0, arr[i] = 1
    arr[i] != x
2. i = 1, arr[i] = 2
    arr[i] != x
3. i = 2, arr[i] = 6
    arr[i] != x
4. i = 3, arr[i] = 10
    arr[i] != x
5. i = 4, arr[i] = 13
    arr[i] != x
6. i = 5, arr[i] = 20
    arr[i] = x
    element found, return i = 5

Time Complexity: 

Time complexity is O(n) where 'n' is the number of elements in the array.
Runtime of our algorithm is linear as in the worst case, the key to be searched (x) would not be present in the array and we would end up searching the whole array.  

GeeksForGeeks: linear search example

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal

Comments

Post a Comment

Popular posts from this blog

Segregate Even Odd value nodes in a linked list

Image
Given the head of a singly linked list, segregate even value nodes with odd value nodes such that all the even value nodes come before all the odd value nodes in the order of their appearance. Segregate Even and Odd value nodes Algorithm: Remember the pivot logic we used in QuickSort ? In QuickSort the pivot value was used to separate all the values which are smaller than pivot towards the left of the pivot and all the values greater than pivot value towards the right of the pivot. We will use a similar logic here. 1. Find the first even value node. 2. Bring this node to the start of the linked list. (Call it pivot) 3. Find the next even value node. 4. Insert this node after the pivot and increment pivot one node ahead. 5. Repeat this until we reach Null or None. The algorithm states to bring the first even value node to the start of the linked list and make a pointer pivot point towards it. Whenever we find an even value node, we need to link the previous node to ...
Keep reading

Tree data structure

Image
Tree Data structure Till now we have seen linear data structures such as arrays and linked lists. In these data structures, we had only one child following the previous parent. 5 is parent of 7 7 is parent of 3 3 is parent of 4 Tree are hierarchical data structures. Here each node can have multiple children. A popular implementation of Tree is a Binary tree where each node has at most 2 children (known as the left child and right child). The top most node is known as the root of the tree similar to the head node in a linked list.  The node directly above some node is called its parent. Application: Trees can are used in various applications that we see every day.  For example, the directory structure that we see in our operating systems (file explorer in Windows, finder in MacOS) is a great example of using tree where each folder is a node and each sub folder are its children, the files can be considered as leaf nodes i.e. the bottom most nodes in the ...
Keep reading

Reverse alternate k nodes in a linked list

Image
Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in alternate groups of K nodes. Reversed alternate K nodes in a linked list Algorithm: We discussed Reversing a linked list in groups of K nodes in the previous post. The logic here is also the same, the only difference is that before the recursive call we traverse K more nodes so that we can skip them. """ Perform the skip after reversing the previous k nodes """ count = 0 # traverse the k nodes to be skipped while current is not None and count < k-1: current = current.next count += 1 Code in Python: # Python program to alternately reverse a linked list in group of given size k # Node class class Node: # Constructor to initialise data and next def __init__(self, data=None): self.data = data self.next = None class SinglyLinkedList: # Constructor to initialise head def __init__(self): self...
Keep reading