🗂️
Data Structures
  • Data Structures Manual
  • Arrays
    • Array ADT
    • Linear Search
    • Binary Search
    • Some More Basic Operations
    • Reversing an Array
    • Operations in a Sorted Array
    • Merging Two Arrays
    • Set Operations
    • Finding Missing Elements
    • Duplicates in an Array
    • Getting a Pair whose Sum = K
    • Finding Max & Min in Single Scan
  • Strings
    • Finding the Length of a String
    • Changing Cases in a String
    • Finding Number of Vowels, Consonants & Words
    • Reversing a String
    • Checking for Palindrome
    • Duplicates in a String
    • Checking if Strings are Anagrams
    • Permutations of a String
  • Singly Linked List
    • Displaying the Nodes
    • Counting the Nodes
    • Sum of all Nodes
    • Finding the Maximum Element
    • Searching in a Node
    • Inserting a Node
    • Inserting a Node in Sorted List
    • Deleting a Node
    • Checking if List is Sorted
    • Removing Duplicates from a List
    • Reversing a Linked List
    • Concatenating Two Lists
    • Detecting a Loop in Linked List
    • Merge Two Sorted Lists
    • Finding the Middle Node
  • Cirular Linked List
    • Displaying the Nodes
    • Inserting a Node
    • Deleting a Node
  • Doubly Linked List
    • Inserting a Node
    • Deleting a Node
    • Reversing a Doubly Linked List
    • Circular Doubly Linked List
  • Stack
    • Stack Using Array
    • Stack Using Linked List
    • Balancing Parenthesis
    • Infix to Postfix
    • Evaluation of Postfix Expression
  • Queue
    • Queue using Array
    • Queue using Linked List
    • Double Ended Queue
  • Binary Tree
    • Creating a Binary Tree using Queue
    • Recursive Tree Traversals
    • Iterative Tree Traversals
    • Level Order Traversal
    • Counting Nodes in a Binary Tree
    • Finding the Height of Tree
    • Finding Sum of All Nodes
  • Binary Search Tree
    • Searching in a BST
    • Inserting in a BST
    • Deleting in a BST
  • AVL Tree
    • Inserting in an AVL Tree
    • AVL Tree Rotations
    • Deleting in an AVL Tree
  • Heap
    • Inserting in a Heap
    • Deleting in a Heap
    • Heapify
Powered by GitBook
On this page
  • Basic Linear Search
  • Improving Linear Search
  • Transposition Method
  • Move to Head

Was this helpful?

  1. Arrays

Linear Search

Implementation of linear search and methods to improve it

Basic Linear Search

In linear search, each element of the array is scanned through a for loop and is checked if it same as the element that is to be found i.e key. If found, the index at which the element was found is returned or else, -1 is returned.

Time Complexity : O(n)

int linearSearch(struct Array arr, int key) {
    
    for (int i = 0; i < arr.length; i++) {
        if (arr.A[i] == key) {
            return i;
        }
    }
    return -1;
    
}

Improving Linear Search

Linear search can be improved by two techniques :

  • Transposition method

  • Move to head

Transposition Method

This method works on the concept that if an element is searched for in an array, chances are that it may be searched for again. Therefore, before returning the index of found element, we swap the element with (i-1)th element and return i-1 instead of i.

int linearSearch(struct Array *arr, int key) {

    for (int i = 0; i < arr -> length; i++) {
        if (arr -> A[i] == key) {
            swap(&arr -> A[i], &arr -> A[i-1]);
            return i-1;
        }
    }
    return -1;    

}

void swap(int *x, int *y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

Move to Head

This method is similar to transposition method except that the found element is swapped with first element i.e 0th index element instead of (i-1)th element. This reduces the time complexity on searching the same element to O(1).

int linearSearch(struct Array *arr, int key) {

    for (int i = 0; i < arr -> length; i++) {
        if (arr -> A[i] == key) {
            swap(&arr -> A[i], &arr -> A[0]);
            return 0;
        }
    }
    return -1;    

}

void swap(int *x, int *y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

Contributed by Nitin Ranganath

PreviousArray ADTNextBinary Search

Last updated 4 years ago

Was this helpful?