A simple approach is to do the Linear Search, i.e., start from the leftmost element of arr[] and one by one compare x with each element of arr[], if x matches with an element, return the index. If x doesn’t match with any of elements, return -1
Program -
int search (int arr[], int n, int x){ int i; for (i=0; i<n; i++) if (arr[i] == x) return i; return -1;}
The time complexity of above algorithm is O(n).
A better approach for searching an element in a sorted list is Binary Search. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Logn). In Binary Search, we basically ignore half of the elements just after one comparison.
2) If x matches with middle element, we return the mid index.
3) Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4) Else (x is smaller) recur for the left half.
Recursive implementation of Binary Search -
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x) return mid;
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
(result == -1) ? printf("Element is not present in array") : printf("Element is present at index %d", result);
return 0;
}
Iterative implementation of Binary Search -
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
(result == -1) ? printf("Element is not present in array") : printf("Element is present at index %d", result);
return 0;
}
