Java Binary Search with Recursion


  • 7
    A

    We can take advantage of the fact that the array is sorted (although rotated).

    1. Figure out if left half is sorted

      1.1. If the target is on left side, continue binary search on left half.

      1.2 If not, it must of in the right half.

    2. Similarly figure out if right half is sorted

      2.1. If the target is on right side, continue binary search on right half.

      2.2 If not, it must of in the left half.

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

      //6,7,1,2,3,4,5
      public int search (int[] nums, int first, int last, int target){
      if (first > last) return -1;

       int mid = (first + last) / 2;
       if (nums[mid] == target) return mid;
       
       if (nums[first] <= nums[mid]) // Left side is sorted
           if (target <= nums[mid] && target >= nums[first]) // target is on left side
               return search (nums, first, mid - 1, target);
           else // target is on the right side
               return search (nums, mid + 1, last, target);
       if (nums[mid] <= nums[last])// Right side is sorted
           if (target >= nums[mid] && target <= nums[last]) // target is right side
               return search (nums, mid + 1, last, target);
           else // target is on left side
               return search (nums, first, mid - 1, target);
       
       return -1;
      

      }


Log in to reply
 

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