Searching an element in an array

Search whether the given key is present or not in the array.

Input

arr[5] = {10, 30, 5, 100, 4};

key = 30

Output

"Search Found"

Input

arr[5] = {10, 30, 5, 100, 4};

key = 500

Output

"Search Not Found"

Algorithm

1. Iterate the array using the loop.

2. Check whether the given key present in the array i.e. arr[i] == key.

3. If yes,

print "Search Found".

4. Else

print "Search Not Found".

Search Found

Let's take an array of 5 elements.

34, 2, 23, 100, 60.

If we search element 100, the execution will be,

1. 34 != 100. Move to the next element.

2. 2 != 100. Move to the next element.

3. 23 != 100. Move to the next element.

4. 100 == 100. Search Found.

Search Not Found

If we search element 1000, the execution will be,

1. 34 != 1000. Move to the next element.

2. 2 != 1000. Move to the next element.

3. 23 != 1000. Move to the next element.

4. 100 != 1000. Move to the next element.

5. 60 != 1000. Search Not Found.

Animated Tutorial

Implementation of searching an element in an array

Example

/*
 * Program  : Searching an element in the array
 * Language : C
 */

#include<stdio.h>

#define size 5

int main()
{
    int arr[size] = {34, 2, 23, 100, 60};
    int key,i,flag = 0;

    printf("Enter element to search\n");
    scanf("%d",&key);

    /*
     * iterate the array elements using loop
     * if any element matches the key, set flag as 1 and break the loop
     * flag = 1 indicates that the key present in the array
     * if execution comes out of loop and the flag remains 0, print search not found
     */

    for(i = 0; i < size; i++)
    {
        if(arr[i] == key)
        {
            flag = 1;
            break;
        }
    }

    if(flag == 1)
        printf("Search Found\n");
    else
        printf("Search Not Found\n");

    return 0;
}

Time Complexity Analysis - Searching for an element in an array

Worst Case - O(N)

If the key present in arr[N - 1] (last index), the for loop will work for N times.

Where N is the number of elements in the array.

Hence the time complexity will be O(N).

Best Case - O(1)

If the key present in arr[0], the for loop will break after its first iteration.

So the time complexity will be O(1).

Useful Resources

1. https://www.log2base2.com/C/array/arrays-in-c.html [Why do we need array?]
2. https://www.log2base2.com/C/array/declaration-and-initialization-of-array-in-c.html [Declaration and Initialization of array]