Write a program to search an element in an array. Given a sorted array, how do you search an element in an array. Think for a moment how do you solve this problem.
You can use multiple approaches to find the solution of this problem. But try to solve this problem in minimum time complexity.
First Approach : You can solve this problem in O(n) time using Linear Search.
Using Linear Search you can compare an element (value to searched for) with each element of an array . If the element is found then return the index/position of an element.
Search an Element in an Array using Linear Search
Linear search is a simple searching algorithm in which element (value to be searched) is compared with each element of an array. If the element is found then it’s index is returned. The time complexity of a Linear Search is O(n).
Find missing number in an array .
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <stdio.h> /* Function that takes arr,length and number as an argument. */ int search(int arr[],int len,int num){ int i; /* Traverse an array */ for(i = 0;i < len; i++){ /* If number is found, return it's index. */ if(arr[i] == num) { return i; break; } } return -1; } int main(void) { int arr[] = {1,3,5,6,7,8,9}; /* Suppose we have to find 8 .*/ int num = 8; int size = sizeof(arr)/sizeof(arr[0]); int pos; pos = search(arr,size,num); if(pos == -1){ printf("Number is not found"); } else { printf("Number is found at %d position",pos); } return 0; } |
PHP Function to Implement Linear Search
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/* Take three argument * $array : array * $len : length of an array * $num : number to be searched */ function search($arr, $len, $num){ for($i = 0;$i < $len; $i++){ /* If number is found, return it's index. */ if($arr[$i] == $num){ return $i; break; } } return -1; } $arr = array(1,3,5,6,7,8,9); /* Suppose we have to find 8 .*/ $num = 8; $len = count($arr); $pos = search($arr, $len, $num); if($pos == -1){ echo "Number is not found"; } else { echo "Number is found at ".$pos. " position"; } |
Second Approach : You can solve this problem in O(logn) time using Binary Search.
Search an Element in an Array using Binary Search
We have seen the implementation of Linear search. Now we use Binary search algorithm which is more efficient than Linear Search. If you are not familiar with binary search, then check my previous posts the link of which is given below.
If you are not familiar with a binary search, then check my previous posts the link of which is given below.
Binary search algorithm & it’s time complexity
Implementation of Binary search using recursion .
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <stdio.h> int main(void) { /* Suppose input array is .*/ int arr[] = {1,4,6,9,11,23,27}; // Let's assume i have to find the position of 11 int num=11; int low = 0,mid; int high = (sizeof(arr)/sizeof(arr[0]))-1; while(low <= high){ // Calculate mid value mid = (low + high)/2; if(arr[mid] == num){ printf("Number is found at %d index",mid); return 0; } else if(arr[mid]<num){ low = mid + 1; }else{ high = mid-1; } } // If number is not found printf("Number not found"); return 0; } |
Using array_search() to search an element in an array – PHP
array_search() function – It searches the array for a given value and returns the corresponding key if successful.
|
1 2 3 4 5 6 7 8 9 |
/* Declare an array. */ $arr=array(1,3,5,6,7,8,9); /* Search the position of 8. */ echo array_search(8,$arr); /* Print 5. */ |
