java solution


  • 0
    2

    worst case is O(n). e.g. find 0 in 111111111110111.

    public class Solution {
        public boolean search(int[] nums, int target) {
            return search(nums, target, 0, nums.length - 1);
        }
        private boolean search(int[] nums, int target, int lo, int hi) {
            if (lo > hi) return false;
            int mid = (lo + hi) / 2;
            if (nums[mid] == target) return true;
            if (nums[mid] > nums[lo]) {
                if (target < nums[lo] || target > nums[mid]) return search(nums, target, mid + 1, hi);
                else return search(nums, target, lo, mid - 1);
            }
            else if (nums[mid] < nums[hi]) {
                if (target > nums[hi] || target < nums[mid]) return search(nums, target, lo, mid - 1);
                else return search(nums, target, mid + 1, hi);
            }
            else return search(nums, target, lo, mid - 1) || search(nums, target, mid + 1, hi);
        }
    }
    

Log in to reply
 

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