[Concise C++ with explanation] Binary search


  • 0
    H
    class Solution {
    public:
        bool search(vector<int>& nums, int target) {
            int left = 0, right = nums.size() - 1;
            while (left <= right) {
                /// Skip the duplicates on two boundaries.
                while (left < right && nums[left] == nums[right]) ++left;
                while (left < right && nums[right] == nums[right - 1]) --right;
                
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) return true;
                
                /// If the lower half is in order.
                if (nums[left] <= nums[mid]) {
                    /// If target is within the lower search range.
                    if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                    else left = mid + 1;
                /// If the upper halp is in order.
                } else {
                    /// If target is within the upper search range.
                    if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                    else right = mid - 1;
                }
            }
            return false;
        }
    };
    

    Time complexity: In worst case is O(n)


Log in to reply
 

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