Given a sorted array arr[] of size N and an integer key, the task is to find the index at which key is present in the array. The given array has been obtained by reversing subarrays {arr[0], arr[R]} and {arr[R + 1], arr[N – 1]} at some random index R. If the key is not present in the array, print -1.
Examples:
Input: arr[] = {4, 3, 2, 1, 8, 7, 6, 5}, key = 2
Output: 2Input: arr[] = {10, 8, 6, 5, 2, 1, 13, 12}, key = 4
Output: -1
Naive Approach: The simplest approach to solve the problem is to traverse the array and check if key is present in the array or not. If found, then print the index. Otherwise, print -1.
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to apply a modified Binary Search on the array to find key. Follow the steps below to solve this problem:
- Initialize l as 0 and h as N – 1, to store the indices of the boundary elements of a search space for the binary search.
- Iterate while l is less than or equal to h:
- Store the middle value in a variable, mid as (l+h)/2.
- If arr[mid] is equal to key, then print mid as the answer and return.
- If arr[l] is greater than or equal to arr[mid], this means the random index lies on the right side of mid.
- If the value of key is between arr[mid] and arr[l] then update h to mid-1
- Otherwise, update l to mid+1.
- Otherwise, it means that the random point lies to the left side of mid.
- If the value of key is between arr[h] and arr[mid], update l to mid+1.
- Otherwise, update h to mid-1.
- Finally, print -1 if key is not found.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to search an element in a// sorted array formed by reversing// subarrays from a random indexint find(vector<int> arr, int N, int key){ // Set the boundaries // for binary search int l = 0; int h = N - 1; // Apply binary search while (l <= h) { // Initialize the middle element int mid = (l + h) / 2; // If element found if (arr[mid] == key) return mid; // Random point is on // right side of mid if (arr[l] >= arr[mid]) { // From l to mid arr // is reverse sorted if (arr[l] >= key && key >= arr[mid]) h = mid - 1; else l = mid + 1; } // Random point is on // the left side of mid else { // From mid to h arr // is reverse sorted if (arr[mid] >= key && key >= arr[h]) l = mid + 1; else h = mid - 1; } } // Return Not Found return -1;}// Driver Codeint main(){ // Given Input vector<int> arr = { 10, 8, 6, 5, 2, 1, 13, 12 }; int N = arr.size(); int key = 8; // Function Call int ans = find(arr, N, key); cout << ans;}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachimport java.util.*;public class GFG {// Function to search an element in a// sorted array formed by reversing// subarrays from a random indexpublic static int find(Vector<Integer> arr, int N, int key){ // Set the boundaries // for binary search int l = 0; int h = N - 1; // Apply binary search while (l <= h) { // Initialize the middle element int mid = (l + h) / 2; // If element found if (arr.get(mid) == key) return mid; // Random point is on // right side of mid if (arr.get(l) >= arr.get(mid)) { // From l to mid arr // is reverse sorted if (arr.get(l) >= key && key >= arr.get(mid)) h = mid - 1; else l = mid + 1; } // Random point is on // the left side of mid else { // From mid to h arr // is reverse sorted if (arr.get(mid) >= key && key >= arr.get(h)) l = mid + 1; else h = mid - 1; } } // Return Not Found return -1;}// Drive Codepublic static void main(String args[]) { Vector<Integer> arr = new Vector <Integer>(); arr.add(10); arr.add(8); arr.add(6); arr.add(5); arr.add(2); arr.add(1); arr.add(13); arr.add(12); int N = arr.size(); int key = 8; // Function Call int ans = find(arr, N, key); System.out.println( ans);}}//This code is contributed by SoumikMondal |
Python3
# Python program for the above approach# Function to search an element in a# sorted array formed by reversing# subarrays from a random indexdef find(arr, N, key): # Set the boundaries # for binary search l = 0 h = N-1 # Apply binary search while l <= h: # Initialize the middle element mid = (l+h)//2 # If element found if arr[mid] == key: return mid # Random point is on # right side of mid if arr[l] >= arr[mid]: # From l to mid arr # is reverse sorted if arr[l] >= key >= arr[mid]: h = mid-1 else: l = mid+1 # Random point is on # the left side of mid else: # From mid to h arr # is reverse sorted if arr[mid] >= key >= arr[h]: l = mid+1 else: h = mid-1 # Return Not Found return -1# Driver Codeif __name__ == "__main__": # Given Input arr = [10, 8, 6, 5, 2, 1, 13, 12] N = len(arr) key = 8 # Function Call ans = find(arr, N, key) print(ans) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to search an element in a// sorted array formed by reversing// subarrays from a random indexstatic int find(List<int> arr, int N, int key){ // Set the boundaries // for binary search int l = 0; int h = N - 1; // Apply binary search while (l <= h) { // Initialize the middle element int mid = (l + h) / 2; // If element found if (arr[mid] == key) return mid; // Random point is on // right side of mid if (arr[l] >= arr[mid]) { // From l to mid arr // is reverse sorted if (arr[l] >= key && key >= arr[mid]) h = mid - 1; else l = mid + 1; } // Random point is on // the left side of mid else { // From mid to h arr // is reverse sorted if (arr[mid] >= key && key >= arr[h]) l = mid + 1; else h = mid - 1; } } // Return Not Found return -1;}// Driver Codepublic static void Main(){ // Given Input List<int> arr = new List<int>(){ 10, 8, 6, 5, 2, 1, 13, 12 }; int N = arr.Count; int key = 8; // Function Call int ans = find(arr, N, key); Console.Write(ans);}}// This code is contributed by ipg2016107 |
Javascript
<script>// Javascript program for the above approach// Function to search an element in a// sorted array formed by reversing// subarrays from a random indexfunction find(arr, N, key){ // Set the boundaries // for binary search let l = 0; let h = N - 1; // Apply binary search while (l <= h) { // Initialize the middle element let mid = Math.floor((l + h) / 2); // If element found if (arr[mid] == key) return mid; // Random point is on // right side of mid if (arr[l] >= arr[mid]) { // From l to mid arr // is reverse sorted if (arr[l] >= key && key >= arr[mid]) h = mid - 1; else l = mid + 1; } // Random point is on // the left side of mid else { // From mid to h arr // is reverse sorted if (arr[mid] >= key && key >= arr[h]) l = mid + 1; else h = mid - 1; } } // Return Not Found return -1;}// Driver Code // Given Input let arr = [ 10, 8, 6, 5, 2, 1, 13, 12 ]; let N = arr.length; let key = 8; // Function Call let ans = find(arr, N, key); document.write(ans);// This code is contributed by _saurabh_jaiswal</script> |
Output:
1
Time Complexity: O(log(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
