Search in Rotated Sorted Array II

You are given an integer array nums sorted in ascending order (not necessarily distinct values), and an integer target.
Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,4,4,5,6,6,7] might become [4,5,6,6,7,0,1,2,4,4]).
If target is found in the array return its index, otherwise, return -1.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Approach

Java

public class SearchRotatedSortedArrayII {
    public static void main(String[] args) {
        int[] nums = { 2, 5, 6, 0, 0, 1, 2 };
        int target = 0;
        System.out.println(search(nums, target));
    }

    static boolean search(int[] nums, int target) {
        return fun(nums, target, 0, nums.length - 1);
    }

    static boolean fun(int[] nums, int target, int low, int high) {
        // base case
        if (low > high)
            return false;

        // calculate mid point
        int mid = (low + high) / 2;

        // if mid value is same as target then return true
        if (nums[mid] == target)
            return true;

        // call for left and right subparts
        return fun(nums, target, low, mid - 1) ||
                 fun(nums, target, mid + 1, high);
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

bool fun(vector<int> &nums, int target, int low, int high)
{
    //base case
    if (low > high)
        return false;

    //calculate mid point
    int mid = (low + high) / 2;

    //if mid value is same as target then return true
    if (nums[mid] == target)
        return true;

    //call for left and right subparts
    return fun(nums, target, low, mid - 1) || fun(nums, target, mid + 1, high);
}
bool search(vector<int> &nums, int target)
{
    return fun(nums, target, 0, nums.size() - 1);
}

int main()
{
    vector<int> nums = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    if (search(nums, target))
        cout << "true";
    else
        cout << "false";
    return 0;
}