Searching in C++: Sequential Searching, Binary Searching
Searching in one-dimensional array:
Searching in C++ – The process of finding a specific data item from a given list of values is called searching. The search is successful if the specified data item is found during Searching in C++ process and is declared unsuccessful otherwise. Search operation is terminated as soon as the required data item is found. However, it is possible that more than one instance of the search item may exist in the given list.
A variety of search methods can be used(depending on the situation) for searching information. The most commonly used search methods are as follows:
- Sequential search
- Binary search
Sequential Searching in C++:
A sequential search is also known as serial or linear search. It is a very simple and straight forward technique to search a specified data item in an unordered list. The specified data item is searched in the list sequentially, i.e. starting from the first data item up to the required data item of the list in a sequence.
Using a sequential search, the following procedure is adopted:
- The required value is compared with the first value of the list.
- It the required value matches with the first value, the search operation is declared successful and is stopped. Suppose we want to search value 63 in the list of value as shown in figure. This value exists at location 6 and 9. The search operation is terminated at position 6.
- If the required value does not match with the first value of the list, it is compared with the second value. the search process continues till the value is found or end of the list is reached. Suppose we want to search 66 in the list of values as shown in figure. This value does not exist in the list as given below. The search operation is terminated at the end of the list.
The sequential search is slow and is used for only small list of data. This method is not recommended for large amount of data because some more efficient method are available for large and complex search.
Example: how to use sequential searching in c++ for search value in array list and display there position on the screen:
|
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 |
#include <iostream> using namespace std; int main() { int arr[5], n, i, pos; i=0; while(i<=4) { cout<<" enter value in element "<<i<<" :"; cin>>arr[i]; i++; } pos = 0; cout<<" enter any value :"; cin>>n; i=0; while(i<=5) { if(n==arr[i]) { pos=i+1; break; } i++; } if(pos==0) cout<<" value not found"<<endl; else cout<<" Value found at position = "<<pos<<endl; } |
When the element not found in the list
Example: how to find maximum value and its location in the array using sequential Searching in C++:
|
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 |
#include <iostream> using namespace std; int main() { float arr[5], max; int loc, i=0; while(i<=9) { cout<<" enter value in element "<<i<<" :"; cin>>arr[i]; i++; } max=arr[0]; i=1; while(i<=9) { if(max<arr[i]) { max = arr[i]; loc=i; } i++; } cout<<"\nMaximum value is :"<<max<<endl; cout<<"Location of the value in array :"<<loc+1; } |
Binary Searching in C++:
The binary searching technique is used to search a specified data value in an ordered list(sorted in ascending or descending order). The binary Searching in C++ is very fast as compared to sequential Searching in C++. It is used to search the large-size list to find a specific value.
In binary searching, the search process is started from the middle of the sorted list. If the required value is in the middle of the list then the searching process is successful and is stopped at that point; otherwise, one of two halves of the list is selected for further Searching in C++. The main idea of the binary search is to repeatedly cut a list into two halves with every comparison.
Suppose an array “abc” with 10 value in sorted order as shown in the following figure
Following steps explain the binary Searching in C++ for finding a specific value in the above array. Suppose we want to search the value 12 in the above array.
Step-1:
Divide the array into two halves such as: mid =(start + end)/2. In the above case, value of start is 0, while end is 9. So value of mid is 4. The value mid[4] (i.e. 23) is greater than 12. The required value (i.e. 12) exists on the left half side of the array, i.e. 0 to 3.
Step-2:
Divide again left side of the array from 0 to 3. In this case, new values of start and end are 0 and 3 (end = mid-1) respectively. Mid = (start + end)/2. So new value of mid is 1. The value of mid[1] (i.e. 4) is less than 12. The required value (i.e. 12 ) exists on the right half side, i.e. 2 to 3.
Step-3:
Divide again array from 2 to 3. In this case, new values of start and end are 2 and 3 (start = mid +1) respectively. Mid = (start+end)/2. So new value of mid is 2. The value of mid[2] (i.e. 7) is less than 12. The required value (i.e. 12) exists on the right half side, i.e. 3 to 3.
Step-4:
Divide again array from 3 to 3. In this case, new values of start and end are 3 and 3 (start = mid + 1) respectively. Mid = (start + end)/2. So new values of mid is 3. The value of mid[3] (i.e. 12) is equal to 12.t the new value is located at position3. The search process is terminated.
Example: write a program that initializes data into one-dimensional array and searches the value in the array using binary searching in c++:
|
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 |
#include <iostream> using namespace std; int main() { int abc[10]={1,3,9,15,78,87,95,103,124,352}; int loc, num, i, m, s=0,e=9; loc=0; cout<<" Enter any value: "; cin>>num; while(s<e) { m=(s+e)/2; if(num==abc[m]) { loc= m+1; break; } else if(num<abc[m]) e=m-1; else s=m+1; } if(loc==0) cout<<" Value not found"<<endl; cout<<" Value found at position = "<<loc<<endl; } |
When a value not found in the array, the following output will display
