C++ Programming Code Examples

C++ > Sorting Searching Code Examples

C++ Program to Perform Searching Based on Locality of Reference



C++ Program to Perform Searching Based on Locality of Reference

- Searching based on Locality of Reference and also called Principle of locality.
- According to this principle, depending on the memory access pattern data elements are reallocated.
- In general search, 80% time only specific 20% of data is accessed.
- The sequential searching approach is used.
- The time complexity of search is O(n).

- Assign data element to the array.
- Sequentially search the element in the array.
- If element found, delete it from the array and add at the beginning of the array.
- Exit.

#include<iostream>
 
using namespace std;
 
// A function to perform linear search.
int Search(int *a, int n, int item)
{
	int i,j;
	for(i = 0; i < n; i++)
	{
		// Linearly search for the item.
		if(item == a[i])
		{
			cout<<"The element "<<item<<" found at "<<i<<" index.";
			// Break if the item is found.
			break;
		}
		// If index reaches to the end then the item is not there. 
		if(i == n-1)
		{
			cout<<"\nThe element not found.";
			return -1;
		}
	}
 
	// Shift each element before matched item.
	for(j = i; j > 0; j--)
		a[j] = a[j-1];
 
	// Put the recently searched item at the beginning of the data array.
	a[0] = item;
	return 0;
}
 
int main()
{
	int i, n, a[20]={44, 26, 17, 4, 9, 63, 76, 98, 33, 47, 18, 32, 96, 90, 43, 28, 29, 81, 44, 33};
	char ch;
	// Initial status of the data array.
	cout<<"\nThe status of the array: ";
	for(i = 0; i < 20; i++)
		cout<<a[i]<<" ";
 
	up:
	cout<<"\nEnter the Element to be searched: ";
	cin>>n;
 
	// Print the updated data array.
	if(Search(a, 20, n) != -1)
	{
		cout<<"\nThe status of the array after this search: ";
		for(i = 0; i < 20; i++)
			cout<<a[i]<<" ";
	}
 
	// Ask user to enter choice for further searching.
	cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
	cin>>ch;
	if(ch == 'y' || ch == 'Y')
		goto up;
 
	return 0;
}