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; }