C++ program to search for elements in a sorted and rotated array

We get a sorted array rotated around a point. We also get a key to search in the array. The logic used to search for elements in this rotated array is -

• First, we find the middle element of the array. If the key exists, we return that the key exists in the array.

• If the key is not in the middle, we can see if the left part of the array (from left to center) is sorted. If it's sorted, you can look for the key on the left, otherwise you can look for the key on the right (mid 1, right)

• If the key is not found in the middle, and the left part is not sorted, then we will sort the right part, and then we can see if the key exists in the right part, or we will search the left part of the array in the right part side

• Otherwise we return not found.

Let’s look at some input and output scenarios below -

Imagine there is an array consisting of its elements. For example, 2, 5, 7, 9, 11, after rotation, become 5, 9, 11, 2, 7. Suppose the array key is 2.

Input: arr[] = {5, 9, 11, 2, 7}, Key=2
Output: Element "2" found at 3rd index

Let's assume another scenario where the key is not in the specified array.

Input: arr[] = {10, 23, 45, 77, 84}, Key=90
Output: Element "90" not found.

algorithm

The following steps are implementation methods.

• Find the middle element of the array.

• Split the array into two parts. (center = left right) / 2

• Check whether key is an intermediate element.

• Else if , checks the element on the left side of the array and it is sorted

• else if, check the right element (mid 1, right)

• Otherwise if, sort the left part and check

• Otherwise, return the element not found.

Example

For example, suppose we have an array "2,3,4,5,6,7,8", and the rotated array is "5,6,7,8,2,3,4". The key of this array is 2.

The C implementation of this operation is as follows -

#include <iostream>
#include <vector>
using namespace std;
bool solve(vector<int> arr, int left, int right, int key) {
   if (left > right) {
      return false;
   }
   int mid = (left + right)/2;
   if (arr[mid] == key) {
      return true;
   }
   if (arr[left] <= arr[mid]) {
      if (key >= arr[left] && key <= arr[mid]) {
         return solve(arr, left, mid-1, key);
      }
      return solve(arr, mid+1, right, key);
   }
   if (key >= arr[mid] && key <= arr[right])
      return solve(arr, mid+1, right, key);
   return solve(arr, left, mid-1, key);
}
int main() {
   vector<int> arr = {5, 6, 7, 8, 2, 3, 4};
   int key = 2;
   if(solve(arr, 0, arr.size()-1, key)) cout << key << " is present";
      else cout << key << " is not present";
   return 0;
}

Output

2 is present

in conclusion

Another way to solve this problem is to find the pivot point or index of the array rotation and then do a binary search for the edges. Our method only requires 1 binary search to solve the problem. Whenever we see searching and sorting arrays, we should consider binary search as one of the search methods.

The above is the detailed content of C++ program to search for elements in a sorted and rotated array. For more information, please follow other related articles on the PHP Chinese website!