My AC Java Solution.

  • 1

    is the complexity of the code below O(lgn)?

    public class Solution {
    public boolean search(int[] nums, int target) {
        int n=nums.length;
        if(n==0) return false;
        int start =0; int end = n-1;
        return searchR(start, end, nums, target);
    public boolean searchR(int start, int end, int[] nums,int target) {
            int mid=(start+end)/2;
            //find it
            if(nums[mid]==target) return true;
            //left is sorted
            if(nums[start]<nums[mid]) {
                //and target is in left
                if(nums[start]<=target&&nums[mid]>=target) end=mid-1;
                //otherwise, check right
                else return searchR(mid+1,end,nums,target);
            //right is sorted
            else if(nums[start]>nums[mid]) {
                //and target is in right
                if(nums[mid]<=target&&nums[end]>=target) start=mid+1;
                //otherwise check left side
                else return searchR(start, mid-1, nums, target);
            else {
                //start , end and mid are the same, cannot tell, the divide and try again
                return searchR(start, mid-1, nums, target) || searchR(mid+1, end, nums, target);
        return false;


Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.