Mastering Binary Search: Find First & Last Position in a Sorted Array Efficiently

Finding the First and Last Position of an Element in a Sorted Array.

In this problem, we need to find the first and the last occurrence of a target element in a sorted array. The most efficient approach that we can take is using Binary Search. As the problem statement already mentions that the array is Sorted, we can implement it into our solution. Binary search has a time complexity of O(Log n), making it very efficient. By using this approach, we locate the leftmost and the right most indices separately. Here we find the First occurance and the last occurrence one by one.
In addition to this approach, we can also use Linear Search (O(n)), which is easier to implement. It is easier to understand but is slower for a large array. We shall also see how we implement this approach. We also discuss how an ArrayList-Based approach fails because it returns all occurrences instead of just two indices and uses extra memory which is unnecessary. We try to understand WHY the best choice is Binary Search when dealing with a sorted array.

The Problem Statement:

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:
Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 105
• 109 <= nums[i] <= 109
• nums is a non-decreasing array.
• 109 <= target <= 109

Understanding the Problem Statement

When solving this problem, the first thing we need to recognize is that the given array is sorted in non-decreasing order. This means that any duplicate elements will be adjacent to each other. The task requires us to find the first and last position of a specific target value.

Key Observations:

• If the target exists in the array, it will be found in a continuous range.
• If the target is missing, we return [-1, -1].
• We need an efficient algorithm with O(log n) complexity, meaning binary search is likely the best choice.

How to Think About the Solution:

1. What does the input tell us? Since the array is sorted, this means we can eliminate unnecessary elements efficiently instead of checking each one.
2. What are we looking for? Instead of simply checking if target exists, we specifically need to determine its first and last occurrence.
3. How do we leverage sorting? Since elements are in order, we can divide and conquer using binary search rather than iterating over the array linearly.
4. What’s the expected output? We return two indices: the first and last position of target. If target isn’t present, return [-1, -1].

Approaches to Solve the Problem

Now let's solve this problem. I will solve it in the most optimal way (Binary Search) and the linear way also.

Binary Search Approach (O(log n))

Since the array is sorted, we can efficiently find the first and last occurrence of the target using binary search.

How It Works:

• We use binary search twice: once to find the leftmost (first) occurrence and once to find the rightmost (last) occurrence.
• The key idea is to adjust the left and right pointers differently depending on whether we are looking for the first or last occurrence.
• This ensures that we find both the starting and ending positions in logarithmic time.

Java Implementation:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findFirst(nums, target), findLast(nums, target)};
    }

    private int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1, first = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                first = mid;
                right = mid - 1;  // Keep searching on the left side
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return first;
    }

    private int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1, last = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                last = mid;
                left = mid + 1;  // Keep searching on the right side
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return last;
    }
}

Explanation:

Understanding the Approach

Since the array is sorted, we can use binary search instead of a linear scan to improve efficiency. Instead of one standard binary search, we perform two separate searches:

1. Find the first occurrence of the target.
2. Find the last occurrence of the target.

Each search runs in O(log n) time, making the total complexity O(log n) + O(log n) = O(log n).

Step-by-Step Working

1. Finding the First Occurrence (findFirst function)

• Initialize left = 0, right = nums.length - 1, and first = -1 (default value if the target is not found).
• Perform binary search:
  • Compute mid = left + (right - left) / 2 to avoid integer overflow.
  • If nums[mid] == target:
  • Store mid in first.
  • Move right to mid - 1 (to search on the left for an earlier occurrence).
  • If nums[mid] < target:
  • Move left to mid + 1.
  • If nums[mid] > target:
  • Move right to mid - 1.
• Once the loop ends, first contains the index of the first occurrence, or -1 if the target is absent.

Example Execution

Input: nums = [5, 7, 7, 8, 8, 10], target = 8

Iterations for findFirst:

Left	Right	Mid	nums[mid]	Action
0	5	2	7	Move left to 3
3	5	4	8	Store first = 4, move right to 3
3	3	3	8	Store first = 3, move right to 2 (loop ends)

First occurrence found at index 3.

2. Finding the Last Occurrence (findLast function)

• Initialize left = 0, right = nums.length - 1, and last = -1.
• Perform binary search:
  • If nums[mid] == target:
  • Store mid in last.
  • Move left to mid + 1 (to search on the right for a later occurrence).
  • If nums[mid] < target:
  • Move left to mid + 1.
  • If nums[mid] > target:
  • Move right to mid - 1.
• Once the loop ends, last contains the index of the last occurrence, or -1 if the target is absent.

Example Execution

Input: nums = [5, 7, 7, 8, 8, 10], target = 8
Iterations for findLast:

Left	Right	Mid	nums[mid]	Action
0	5	2	7	Move left to 3
3	5	4	8	Store last = 4, move left to 5
5	5	5	10	Move right to 4 (loop ends)

Last occurrence found at index 4.

Final Output

int[] result = searchRange([5, 7, 7, 8, 8, 10], 8);
result -> [3, 4]

Thus, the target 8 is found at indices [3, 4].

Time Complexity Analysis

Each function (findFirst and findLast) runs in O(log n) due to binary search. Since we run two binary searches, the overall time complexity remains O(log n).

Edge Cases Considered

1. Target Not Found: If the target is missing, both findFirst and findLast return -1, giving [-1, -1].

searchRange([5, 7, 7, 8, 8, 10], 6);// Output: [-1, -1]

Single Element Array: If nums has only one element, the function correctly returns [0, 0] if it matches or [-1, -1] otherwise.
searchRange([8], 8); // Output: [0, 0]

1. searchRange([8], 5); // Output: [-1, -1]
2. All Elements are the Same as Target: The function correctly returns [0, nums.length - 1]. searchRange([8, 8, 8, 8, 8], 8); // Output: [0, 4]

Flow Chart

Linear Search Approach (O(n))

A brute-force approach that scans the entire array to find the first and last occurrence of target.

How It Works:

• We iterate through the array and track the first and last occurrence of target.
• If target is found, update first if it's the first occurrence.
• Keep updating last every time target appears.
• This method works but is slow for large inputs.

Java Implementation:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1, last = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (first == -1) {
                    first = i;
                }
                last = i;
            }
        }
        return new int[]{first, last};
    }
}

Understanding the Approach

Instead of using binary search, this method scans through the entire array once to determine the first and last positions of the target.

Step-by-Step Working

1. Initialize first = -1 and last = -1.

   • These variables store the indices of the first and last occurrence of the target.

2. Iterate through the array using a for loop:

   • If nums[i] == target:
     • If first is -1, update first = i (record the first occurrence).
     • Update last = i (continuously updating to track the last occurrence).

3. Return an array [first, last].

   • If the target is not found, both values remain -1.

Example Execution

Example 1

Input: nums = [5, 7, 7, 8, 8, 10], target = 8

Iterations:

Index	nums[i]	first	last	Action
0	5	-1	-1	No update
1	7	-1	-1	No update
2	7	-1	-1	No update
3	8	3	3	First occurrence found
4	8	3	4	Last updated to 4
5	10	3	4	No update

Output:[3, 4]

Example 2 (Target Not Found)
Input: nums = [5, 7, 7, 8, 8, 10], target = 6
Since 6 is not in the array, first and last remain -1, so the output is:
[-1, -1]

Example 3 (All Elements are Target)
Input: nums = [8, 8, 8, 8, 8], target = 8
Since every element is 8, first = 0 and last = 4, giving:
[0, 4]

Time Complexity Analysis

Since we scan the array once, the time complexity is O(n), where n is the number of elements in nums. This is less efficient than the O(log n) binary search approach for large arrays but works well for small to medium-sized datasets.

Edge Cases Considered

1. Target Not Found → Returns [-1, -1].
2. Single Element Array → Returns [0, 0] if it matches, otherwise [-1, -1].
3. All Elements Are Target → Returns [0, nums.length - 1].

Flow Chart

ArrayList-Based Approach (Why It Fails)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        ArrayList<Integer> retArray = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                retArray.add(i);
            }
        }
        if (retArray.isEmpty()) {
            return new int[] {-1, -1};
        }
        return retArray.stream().mapToInt(num -> num).toArray();
    }
}

Why This Approach to searchRange is Incorrect

In this implementation of searchRange, an ArrayList is used to collect all indices where the target occurs in the array. However, this approach is incorrect because it does not meet the problem's requirement of returning only the first and last occurrence of the target. Instead, it stores all occurrences, leading to incorrect results in certain cases.

Understanding the Issues

1.Returns All Occurrences Instead of Just First & Last

The function collects all indices where nums[i] == target, meaning that if the target appears multiple times, the returned array will contain all occurrences instead of just the first and last index.

Example Failure:

searchRange([5, 7, 7, 8, 8, 10], 8);
// Expected Output: [3, 4]
// Actual Output: 3, 4

searchRange([8, 8, 8, 8], 8);
// Expected: [0, 3]
// Actual: 0, 1, 2, 3

2.Fails When Target is Absent

The function correctly checks if retArray is empty and returns [-1, -1] when the target is missing. However, it unnecessarily uses extra space to store occurrences instead of simply tracking the first and last indices.

3.Inefficient Space Usage

The use of ArrayList increases the space complexity to O(n), whereas an optimal approach can achieve O(1) space by just tracking the first and last occurrence.
Additionally, converting the list to an array using .stream().mapToInt(num -> num).toArray() is an unnecessary overhead.

In conclusion, I would say that the problem of finding the first and last position of an element in a sorted array can be efficiently solved using the Binary Search approach, which offers a time complexity of O(log n). This method leverages the sorted nature of the array to quickly narrow down the search space, making it highly efficient for large datasets. By performing two separate binary searches—one to find the first occurrence and another to find the last occurrence—we can accurately determine the target's range in the array.

While the Linear Search approach is simpler to implement and understand, it is less efficient with a time complexity of O(n), making it unsuitable for large arrays. The ArrayList-Based approach, although intuitive, fails to meet the problem's requirements by returning all occurrences of the target instead of just the first and last indices, and it also incurs unnecessary space overhead.

Therefore, the Binary Search approach stands out as the optimal solution for this problem, balancing both time and space efficiency. It is crucial to choose the right algorithm based on the problem constraints and the nature of the input data to achieve the best performance.