- Problem Statement<\/a><\/li>
- Naive Approach<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- Optimal Approach(With Binary Search)<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- Practice Problem:<\/a><\/li>
- FAQs<\/a><\/li>
- Q.1: Will the binary search approach work if the array has duplicate elements?<\/a><\/li>
- Q.2: What are the base cases for this recursive approach?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given an array of distinct<\/strong> elements, which is formed from some places rotation of a sorted array, find if a given element is present in the array or not.<\/p>\n\n\n\n
<\/figure>\n\n\n\n
Sample Test Cases :<\/strong><\/p>\n\n\n\n
Input 1:<\/strong><\/p>\n\n\n\n
a[] = [4, 5, 6, 7, 8, 9, 1, 2, 3]\n\n\n\n
sum = 6<\/p>\n\n\n\n
Output 1:<\/strong><\/p>\n\n\n\n
2<\/p>\n\n\n\n
Explanation 1:<\/strong><\/p>\n\n\n\n
The value of 2 is found in the array a[]<\/strong> at index 2<\/strong>.<\/p>\n\n\n\n
Input 2:<\/strong><\/p>\n\n\n\n
a[] = [4, 5, 6, 7, 8, 9, 1, 2, 3]\n\n\n\n
sum = 12<\/p>\n\n\n\n
Output 2:<\/strong><\/p>\n\n\n\n
-1<\/p>\n\n\n\n
Explanation 2:<\/strong><\/p>\n\n\n\n
Since the value of 12 is not present in the given array, we return -1.<\/p>\n\n\n\n
Naive Approach<\/h2>\n\n\n\n
The naive approach to solve this problem is to linearly iterate on the array, and check if the current element is equal to the target element or not.<\/p>\n\n\n\n
Code \/ Implementation:<\/strong><\/p>\n\n\n\n
C++ Code<\/span><\/h3>\n\n\n\n
int findInArray(vector < int > & a, int target) {\n return find(a.begin(), a.end(), target) == a.end() ? -1 : find(a.begin(), a.end(), target) - a.begin();\n}<\/pre>\n\n\n\nJava Code<\/span><\/h3>\n\n\n\n
public static int findInArray(int[] a, int target) {\n int found = -1;\n for (int i = 0; i < a.length; i++) {\n if (a[i] == target) {\n found = i;\n break;\n }\n }\n return found;\n}<\/pre>\n\n\n\nPython Code<\/span><\/h3>\n\n\n\n
def findInArray(a, target):\n for i in range(len(a)):\n if a[i] == target:\n return i\n return -1<\/pre>\n\n\n\n
Complexity Analysis:<\/strong><\/p>\n\n\n\n
- Time Complexity: O(n)<\/li>
- Space Complexity: O(1)<\/li><\/ul>\n\n\n\n
Optimal Approach(With Binary Search)<\/h2>\n\n\n\n
We can solve this problem optimally with a single recursive Binary Search<\/strong>. <\/strong>The algorithm is implemented as follows:<\/p>\n\n\n\n
- Initialize the recursive function with 2 pointers, left = 0, and right = n – 1.<\/li>
- Find the mid of the range mid = (left + right) \/ 2.<\/li>
- If the range [left, mid] is sorted,
- If the target lies in that range, recursively go to the range [left, mid].<\/li>
- Else go to the range [mid + 1, right].<\/li><\/ul><\/li>
- Else, we go to the range [mid + 1, right] (since it must be sorted),
- If the target lies in the range, recursively go to the range [mid + 1, right].<\/li>
- Else go to the range [left, mid]. <\/li><\/ul><\/li><\/ul>\n\n\n\n
Implementation:<\/strong><\/p>\n\n\n\n
C++ Code<\/h3>\n\n\n\n
int findInArray(vector < int > & a, int left, int right, int target) {\n if (left > right) {\n return -1;\n }\n int mid = (left + right) \/ 2;\n if (a[mid] == target) {\n return mid;\n }\n if (a[mid] >= a[left]) {\n if (target >= a[left] && target <= a[mid]) {\n return findInArray(a, left, mid - 1, target);\n } else {\n return findInArray(a, mid + 1, right, target);\n }\n } else {\n if (target >= a[mid] && target <= a[right]) {\n return findInArray(a, mid + 1, right, target);\n } else {\n return findInArray(a, left, mid - 1, target);\n }\n }\n}<\/pre>\n\n\n\nJava Code<\/h3>\n\n\n\n
public static int findInArray(int[] a, int left, int right, int target) {\n if (left > right) {\n return -1;\n }\n int mid = (left + right) \/ 2;\n if (a[mid] == target) {\n return mid;\n }\n if (a[mid] >= a[left]) {\n if (target >= a[left] && target <= a[mid]) {\n return findInArray(a, left, mid - 1, target);\n } else {\n return findInArray(a, mid + 1, right, target);\n }\n } else {\n if (target >= a[mid] && target <= a[right]) {\n return findInArray(a, mid + 1, right, target);\n } else {\n return findInArray(a, left, mid - 1, target);\n }\n }\n}<\/pre>\n\n\n\nPython Code<\/h3>\n\n\n\n
def findInArray(a, left, right, target):\n if left > right:\n return -1\n mid = (left + right) \/\/ 2\n if a[mid] == target:\n return mid\n if a[mid] >= a[left]:\n if target >= a[left] and target <= a[mid]:\n return findInArray(a, left, mid - 1, target)\n else:\n return findInArray(a, mid + 1, right, target)\n else:\n if target >= a[mid] and target <= a[right]:\n return findInArray(a, mid + 1, right, target)\n else:\n return findInArray(a, left, mid - 1, target)<\/pre>\n\n\n\n
Complexity Analysis:<\/strong><\/p>\n\n\n\n
- Q.2: What are the base cases for this recursive approach?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code<\/a><\/li>
- Java Code<\/a><\/li>
- Naive Approach<\/a><\/li>
![\"distinct](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/distinct-elements-1024x256.png\")
<\/figure>\n\n\n\n