What is searching in c plus plus language?

Answer 1

Searching in C++ is the same as searching in any language. It is the process of locating a subset of data within a data set, whether to determine if the subset exists or does not exist in the set. The set of data is typically a set of objects contained in an array, a list, a vector, or some other container object that can be iterated one element at a time, while the subset is typically a single object which may or may not exist in the set of objects. In other words, you must search for a specific value in order to ascertain if that value exists in the set.

All search algorithms have a time complexity which can be expressed using big-O notation. The best case is O(1), meaning constant time. That is, the time taken to search for any value in the set is exactly the same, regardless of the value's position in the set. Unfortunately, this is impossible as O(1) can only be guaranteed when the value being sought happens to be the first value in the set or the set only has one value. The worst case is O(n) for a set of n elements, where every value in the set must be inspected. This can occur when the value being sought does not exist or is the final element in the set.

The structure that contains the data can have a large effect on time complexity. For instance, with a linear structure, such as an array, the average time complexity is O(n/2) if the array is in sorted order. However, this can be reduced to O(log n) by starting the search in the middle of the structure rather than at the beginning. If the middle value is greater than the value being sought, you can eliminate all the elements to the right of that value. If it is less, you can eliminate all the values to the right. You then repeat the process using the remaining elements, essentially halving the amount of data to be searched at each stage until there is only one element left to inspect. If it is not the value you are looking for, the value does not exist in the set.