Binary Search: Logic Building & Advanced Problems

Beyond standard sorted arrays, Binary Search is a powerful technique for solving complex algorithmic problems by identifying ordered properties and systematically eliminating half of the search space. This note covers logic building problems involving rotated sorted arrays, handling duplicate elements, tracking rotation points, and index parity search strategies.

---

1. Search in Rotated Sorted Array (Unique Elements)

Problem Description

Given an integer array nums sorted in ascending order with distinct values, which has been rotated at an unknown pivot index, and a target integer, return the index of target if it is in nums, or -1 if it is not.

Intuition & Key Insight

In a rotated sorted array, splitting the array at mid always leaves at least one of the two halves strictly sorted:

1. Compare nums[low] and nums[mid]:
   • If nums[low] <= nums[mid], the left half (low to mid) is sorted.
   • Otherwise, the right half (mid to high) is sorted.
2. Once you identify which half is sorted, check if target falls within the range of that sorted half:
   • If target is in range, adjust high or low to stay within that half.
   • If not in range, discard that half and search the other half.

Example Walkthrough

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0

• Iteration 1: low = 0, high = 6 → mid = 3 (nums[3] = 7).
  • nums[0] (4) <= nums[3] (7) → Left half [4, 5, 6, 7] is sorted.
  • Is target = 0 within [4, 7]? No (0 < 4).
  • Search right half: low = mid + 1 = 4.
• Iteration 2: low = 4, high = 6 → mid = 5 (nums[5] = 1).
  • nums[4] (0) <= nums[5] (1) → Left half [0, 1] is sorted.
  • Is target = 0 within [0, 1]? Yes (0 <= 0 <= 1).
  • Search left portion of this half: high = mid - 1 = 4.
• Iteration 3: low = 4, high = 4 → mid = 4 (nums[4] = 0).
  • nums[4] == target (0). Target found! Return 4.

Output: 4

Python Solution

class Solution:
    def search(self, nums: list, target: int) -> int:
        ans = -1
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid

            # Check if left side is sorted
            if nums[low] <= nums[mid]:
                if nums[low] <= target <= nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            # Right side is sorted
            else:
                if nums[mid] < target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1

        return ans

def main():
    nums = [4, 5, 6, 7, 0, 1, 2]
    k = 0

    sol = Solution()
    print(sol.search(nums, k))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(log N) — One half is eliminated at every step.
• Space Complexity: O(1) — Constant memory usage.

---

2. Search in Rotated Sorted Array II (With Duplicates)

Problem Description

Given a rotated sorted array nums that may contain duplicates, return True if target is present in nums, or False if it is not.

Intuition & Edge Case Handling

When duplicate elements exist, an edge case arises where nums[low] == nums[mid] == nums[high]. For example, in [3, 1, 2, 3, 3, 3, 3], it is impossible to determine which half is sorted by comparing nums[low] and nums[mid].

Resolution Strategy:

• Before checking which half is sorted, shrink the search space from both ends while nums[low] == nums[mid] == nums[high]:

  while low < high and nums[mid] == nums[low] and nums[mid] == nums[high]:
      low += 1
      high -= 1
  

• Once non-identical endpoints are established, proceed with the standard sorted half elimination logic.

Example Walkthrough

Input: nums = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6], target = 3

• Iteration 1: low = 0, high = 9 → mid = 4 (nums[4] = 3).
  • nums[4] == 3 matches target directly! Return True.

Output: True

Python Solution

class Solution:
    def search_in_rotated(self, nums: list, target: int) -> bool:
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = (low + high) // 2

            if nums[mid] == target:
                return True

            # Handle duplicate edge cases where endpoints match mid
            while low < high and nums[mid] == nums[low] and nums[mid] == nums[high]:
                low += 1
                high -= 1

            # Check if left side is sorted
            if nums[low] <= nums[mid]:
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            # Right side is sorted
            else:
                if nums[mid] < target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1

        return False

def main():
    nums = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6]
    k = 3

    sol = Solution()
    print(sol.search_in_rotated(nums, k))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: Average O(log N), Worst Case O(N) when all elements are duplicates and we shrink pointers sequentially.
• Space Complexity: O(1) — In-place traversal.

---

3. Find Minimum in Rotated Sorted Array

Problem Description

Given a rotated sorted array of distinct elements arr, find and return the minimum element in the array.

Intuition & Approach

In a rotated sorted array, the minimum element is located at the rotation pivot:

1. Initialize minimum = float('inf') (or a large baseline integer).
2. Determine which half is sorted:
   • If arr[low] <= arr[mid], the left half is sorted. The smallest element in this half is arr[low]. Update minimum = min(minimum, arr[low]), then eliminate the left half (low = mid + 1).
   • If the right half is sorted, arr[mid] is the smallest in the right half. Update minimum = min(minimum, arr[mid]), then eliminate the right half (high = mid - 1).
3. Return minimum after search completion.

Example Walkthrough

Input: arr = [4, 5, 6, 7, 0, 1, 2, 3]

• Iteration 1: low = 0, high = 7 → mid = 3 (arr[3] = 7).
  • arr[0] (4) <= arr[3] (7) → Left half is sorted.
  • Candidate min: arr[0] = 4. minimum = min(inf, 4) = 4.
  • Move right: low = mid + 1 = 4.
• Iteration 2: low = 4, high = 7 → mid = 5 (arr[5] = 1).
  • arr[4] (0) <= arr[5] (1) → Left half is sorted.
  • Candidate min: arr[4] = 0. minimum = min(4, 0) = 0.
  • Move right: low = mid + 1 = 6.
• Iteration 3: low = 6, high = 7 → mid = 6 (arr[6] = 2).
  • arr[6] (2) <= arr[6] (2) → Candidate min: arr[6] = 2. minimum = min(0, 2) = 0.
  • Move right: low = 7.
• Iteration 4: low = 7, high = 7 → mid = 7 (arr[7] = 3).
  • Candidate min: arr[7] = 3. minimum = min(0, 3) = 0. low = 8.

Output: 0

Python Solution

class Solution:
    def find_minimum(self, arr: list) -> int:
        minimum = 99999999999
        low, high = 0, len(arr) - 1

        while low <= high:
            mid = (low + high) // 2

            # If left side is sorted
            if arr[low] <= arr[mid]:
                minimum = min(minimum, arr[low])
                low = mid + 1
            else:
                minimum = min(minimum, arr[mid])
                high = mid - 1

        return minimum

def main():
    sol = Solution()
    nums = [4, 5, 6, 7, 0, 1, 2, 3]

    print(sol.find_minimum(nums))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(log N) — Logarithmic reduction.
• Space Complexity: O(1) — Single tracker variable.

---

4. Find Number of Array Rotations

Problem Description

Given an array nums of N distinct integers sorted in ascending order and rotated K times to the right, find the rotation count K.

Intuition & Mathematical Relation

Notice that if an array sorted in ascending order is rotated K times:

• Number of rotations K = Index of the minimum element in the array

For example, [4, 5, 6, 7, 0, 1, 2, 3] is rotated 4 times, and element 0 (the minimum) is at index 4.

Approach

We track ans (the index of the minimum element found so far):

1. In each iteration, if the left half is sorted (nums[low] <= nums[mid]), check if nums[low] < nums[ans]. If so, update ans = low. Then move right (low = mid + 1).
2. If the right half is sorted, check if nums[mid] < nums[ans]. If so, update ans = mid. Then move left (high = mid - 1).
3. Return ans.

Example Walkthrough

Input: nums = [4, 5, 6, 7, 0, 1, 2, 3]

• low = 0, high = 7, mid = 3 (nums[3] = 7).
  • nums[0] (4) <= nums[3] (7) → Left half sorted.
  • nums[0] (4) < nums[0] (4) is False, ans = 0. Move right low = 4.
• low = 4, high = 7, mid = 5 (nums[5] = 1).
  • nums[4] (0) <= nums[5] (1) → Left half sorted.
  • nums[4] (0) < nums[0] (4) is True → ans = 4. Move right low = 6.
• Continuation yields ans = 4.

Output: 4

Python Solution

class Solution:
    def find_k_rotation(self, nums: list) -> int:
        ans = 0
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = (low + high) // 2

            # Check if left side is sorted
            if nums[low] <= nums[mid]:
                if nums[low] < nums[ans]:
                    ans = low
                low = mid + 1
            else:
                if nums[mid] < nums[ans]:
                    ans = mid
                high = mid - 1

        return ans

def main():
    nums = [4, 5, 6, 7, 0, 1, 2, 3]
    sol = Solution()

    print(sol.find_k_rotation(nums))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(log N) — Binary search to locate pivot index.
• Space Complexity: O(1) — Constant variable state.

---

5. Single Element in a Sorted Array

Problem Description

Given a sorted array nums consisting of N integers where every element appears exactly twice except for one element which appears exactly once, find and return that single element in O(log N) time and O(1) space.

Intuition & Index Parity Property

Consider an array where elements appear in pairs before the single element:

• Left of single element: Pairs start at even indices and end at odd indices: (even, odd).
  • For example: [1, 1, 2, 2, 3, 3] → indices (0, 1), (2, 3), (4, 5).
• Right of single element: The pattern flips! Pairs start at odd indices and end at even indices: (odd, even).

Algorithm

1. Base cases: array length 1, or single element at index 0 or index N - 1.
2. Compute mid = (low + high) // 2.
3. If nums[mid] != nums[mid - 1] and nums[mid] != nums[mid + 1], nums[mid] is the single element! Return nums[mid].
4. If mid is odd:
   • If nums[mid] == nums[mid - 1], we are in the left pattern (even, odd). The single element lies to the right → low = mid + 1.
   • Else, we are in the right pattern. The single element lies to the left → high = mid - 1.
5. If mid is even:
   • If nums[mid] == nums[mid - 1], we are in the right pattern. Single element is to the left → high = mid - 1.
   • Else, single element is to the right → low = mid + 1.

Example Walkthrough

Input: nums = [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6]

• Initial checks: nums[0] == nums[1] and nums[-1] == nums[-2]. Proceed to loop.
• low = 0, high = 10 → mid = 5 (nums[5] = 3).
  • mid = 5 is odd. nums[5] equals nums[4] (both 3).
  • This matches (even, odd) pattern! Single element is on the right → low = mid + 1 = 6.
• low = 6, high = 10 → mid = 8 (nums[8] = 5).
  • mid = 8 is even. nums[8] equals nums[7] (both 5).
  • Matches right pattern! Move left: high = mid - 1 = 7.
• low = 6, high = 7 → mid = 6 (nums[6] = 4).
  • nums[6] is 4. nums[5] is 3, nums[7] is 5. nums[6] matches neither neighbor!

Output: 4

Python Solution

class Solution:
    def single_element(self, nums: list) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]

        ans = -1
        low, high = 0, len(nums) - 1

        # Check edge boundary elements
        if nums[0] != nums[1]:
            return nums[0]
        if nums[-1] != nums[-2]:
            return nums[-1]

        while low <= high:
            mid = (low + high) // 2

            # Check if mid is the unique element
            if nums[mid] != nums[mid - 1] and nums[mid] != nums[mid + 1]:
                return nums[mid]

            # Index parity checks
            if mid % 2 == 1:
                if nums[mid] == nums[mid - 1]:
                    low = mid + 1
                else:
                    high = mid - 1
            else:
                if nums[mid] == nums[mid - 1]:
                    high = mid - 1
                else:
                    low = mid + 1

        return ans

def main():
    sol = Solution()
    nums = [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6]

    print(sol.find_minimum(nums))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(log N) — Parity-based interval elimination in logarithmic time.
• Space Complexity: O(1) — Zero additional space overhead.