Searching in Arrays

Searching is a process of finding the required data in the array. Searching becomes more important when the length of the array is very large.

Sequential Search

Sequential search is also called linear search or serial search. It is a simple way to search an array for the desired value. It follows the following steps to search a value in array.

• Visit the first element of the array and compare its value with the required value.

• It the value of array matches with the desired value, the search is complete.

• If the value of array does not match, move to next element and repeat same process.

Loops are frequently used to visit elements of array for searching a value. You can start the counter variable of loop from 0 and move it to last index of array. For example, the loop will start the counter variable from 0 and move to 9 if the array has 10 elements.

Example

Write a program that initializes an array. It inputs a value from the user and searches the number in the array.

#include<iostream>
using namespace std;
int main()
{
int arr[10] = { 10,20,30,40,50,60,70,80,90,100};
int i, n, loc=-1;
cout<<"Enter value to find: ";
cin>>n;
for(i=0;i<10;i++)
if(arr[i] == n)
loc=i;
if(loc == -1)
cout<<"Value not found in the array.";
else
cout<<"Value found at index"<<loc;
return 0;
}

Best use case

This search is best used when the list of elements in unsorted and the search is to be performed only once. It is also preferred for list to be small, as the time taken grows with the size of the data.

Time Complexity

• Average O(n)

• Best O(1)

• Worst O(n)

The element to be found may be toward the end of the list or it may not be there at all, so the average time complexity is O(n). The items must be visited one by one until the linear search locates the required element. According to algorithms, this equals O.

As the element to be sought might always be located on the first iteration or the last iteration, the best and worst cases of a search algorithm will be O(1) and O(n), respectively.

Binary Search

Binary search is a quicker method of searching for value in the array. Binary search is very quick but it can only search a sorted array. It cannot be applied on an unsorted array.

• It locates the middle element of array and compares with the search number.

• If they are equal, the search is successful and the index of middle element is returned.

• If they are not equal, it reduces the search to half of the array.

• If the search number is less than the middle element, it searches the first half of array. Otherwise it searches the second half of the array. The process continues until the required number is found or loop completes without successful search.

Example

Write a program that initializes an array of ten integers. It inputs an integer from the user and searches the value in the array using binary search.

#include<iostream>
using namespace std;
int main()

{

    int arr[10] = { 10,20,30,40,50,60,70,80,90,100};

int n, i, mid, start, end, loc;

loc = -1;

start = 0;

end =9;

cout<<"Enter any number to find: ";

cin>>n;

while(start<=end)

{

    mid = (start+end)/2;

if(arr[mid] == n)

{

    loc = mid;

break;

}

else if(n<arr[mid])

end = mid -1;

else 

start = mid+1;

}

if(loc == -1)

 cout<<n<<"not found!"<<"\n";

else

cout<<n<<"found at index "<<loc<<"\n";

return 0;

}

Best use case

When the list of elements is already sorted, this search works well (not always feasible, especially when new elements are frequently being inserted). Due to the algorithm's logarithmic time complexity, the size of the list to be searched can be rather big without a significant reduction in search time.

Time Complexity

• Average O(log n)

• Best O(1)

• Worst O(n)

This search algorithm's average time complexity is O(log n), where n is the number of elements to be searched and 1/n is the number of iterations.

A search algorithm's best and worst cases will be O(1) and O(n), respectively, because the element to be searched can always be located on the first or the last iteration.