Java AC Solution using once binary search


  • 96
    F

    The idea is that when rotating the array, there must be one half of the array that is still in sorted order.
    For example, 6 7 1 2 3 4 5, the order is disrupted from the point between 7 and 1. So when doing binary search, we can make a judgement that which part is ordered and whether the target is in that range, if yes, continue the search in that half, if not continue in the other half.

    public class Solution {
        public int search(int[] nums, int target) {
            int start = 0;
            int end = nums.length - 1;
            while (start <= end){
                int mid = (start + end) / 2;
                if (nums[mid] == target)
                    return mid;
            
                if (nums[start] <= nums[mid]){
                     if (target < nums[mid] && target >= nums[start]) 
                        end = mid - 1;
                     else
                        start = mid + 1;
                } 
            
                if (nums[mid] <= nums[end]){
                    if (target > nums[mid] && target <= nums[end])
                        start = mid + 1;
                     else
                        end = mid - 1;
                }
            }
            return -1;
        }
    }

  • 0
    S

    Thank you for your prompt!


  • 0
    H

    I have one question:

    Why don't consider the case "nums[start] > nums[mid]" and "nums[mid] > nums[end]"?


  • 0
    T

    You want to zero in onto a sorted region without confusing yourself by having 1 pointer in 1 sorted region and the other pointer in the other. The array can be seen as 2 separate sorted regions. Both the cases described above handle each of these regions: i.e. either target will be between start and mid or between mid and end. The cases that you have cited are covered in these 2 cases. For example, nums[start] > nums[mid] when start is in the 1st sorted region and mid is in the 2nd sorted region. When this happens, nums[mid] < nums[end].


  • 0
    T

    Nice! Very easy to understand and generalizable as well. Thanks.


  • 0
    H

    Thank you for sharing


  • 0
    Z
    This post is deleted!

  • 1
    J

    Not until reading your code that I realized when leetcode says an array is sorted,it means non-descending order...Thanks anyway and well done with your excellent work ! But I think it's better to use "else" than "if (nums[mid] <= nums[end])" , just personal opinion ; )


  • 0
    F

    No such possibility since the array is rotated at only one certain pivot


  • 2
    K

    it's kinda tricky to grasp binary search boundary conditions..how to make it easier?


  • 0
    M

    Hi @tjbstuff, here is my simple technique (actually it is quite common!!). when performing search:

    while (left < right-1) { ... if (target < nums[mid]) { right = mid; } if (target > nums[mid]) { left = mid; } ...}
    

    after that, you just need to do some simple post-processing:

    if (nums[left] == target) { return left; }
    if (nums[right] == target) { return right; }
    return -1;
    

    Except for the most standard binary search, when coming to first/last occurance etc., this simple trick will make your life a lot easier.


  • 0
    V

    C++ version of the solution.

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int i = 0, j = nums.size()-1;
            while(i < j){
                int mid = i + (j-i)/2;
                if(nums[mid] < target){
                    if(target > nums[j] && nums[mid] <= nums[j])j = mid;
                    else i = mid+1;
                }
                else if(nums[mid] > target){
                    if(target < nums[i] && nums[mid] >= nums[i])i = mid+1;
                    else j = mid;
                }
                else return mid;
            }
            return nums[i] == target?i:-1;
        }
    };

  • 1

    The solution has two if's inside the loop which modifies the start and end variable I think it could be if and else, because it seems as if both the if statements would be executed but actually only one of the both gets executed at any iteration.


  • 0
    D

    it's told that the array is sorted, but not mention whether it's sorted by desc. Give one test case, [3,2,1,5,4], target=2. Your solution return -1...


  • 0
    C

    Brilliant !!


  • 0
    L

    thank you for helping me.


  • 0
    A
    This post is deleted!

  • 0
    U

    you can add an else at the beginning of second if statement like "else if (nums[mid] <= nums[end])"


Log in to reply
 

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