mediumBinary SearchPattern: Binary Search

Find Closest Element in Sorted Array Solution

Problem Statement

Given a strictly increasing array of integers `arr` and an integer `target`, find the index of the element in `arr` that is closest to `target`. If there are multiple elements equally close, return the index of the smaller element.

Examples

Example 1:

Input:{"arr":[1,3,5,7,9],"target":6}

Output:2

Explanation: The elements are 1, 3, 5, 7, 9. The target is 6. The differences are |1-6|=5, |3-6|=3, |5-6|=1, |7-6|=1, |9-6|=3. The minimum difference is 1, achieved by elements 5 (at index 2) and 7 (at index 3). Since the problem asks for the index of the element with the smaller value in case of ties, we return the index of 5, which is 2.

Constraints

1 <= arr.length <= 10^5
-10^9 <= arr[i] <= 10^9
arr is strictly increasing.
-10^9 <= target <= 10^9

Time: O(log n) Space: O(1)

Use binary search to efficiently narrow down the search space. During the binary search, continuously update the closest element found so far. After the binary search loop finishes, compare the elements at the final `left` and `right` pointers (or adjacent indices) to determine the absolute closest element, handling ties by selecting the smaller index.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

import math

def find_closest_element_in_sorted_array(arr, target):
    if not arr:
        return -1

    left, right = 0, len(arr) - 1
    closest_index = 0

    while left <= right:
        mid = left + (right - left) // 2
        
        diff_mid = abs(arr[mid] - target)
        diff_closest = abs(arr[closest_index] - target)

        if diff_mid < diff_closest:
            closest_index = mid
        elif diff_mid == diff_closest:
            closest_index = min(closest_index, mid)

        if arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid - 1
        else:
            return mid # Exact match is the closest

    # After the loop, the 'left' pointer will be at the first element greater than target
    # and 'right' will be at the first element smaller than target.
    # We need to check these two potential candidates.
    
    # Check the element at 'left' if it's within bounds
    if left < len(arr):
        diff_left = abs(arr[left] - target)
        diff_closest = abs(arr[closest_index] - target)
        if diff_left < diff_closest:
            closest_index = left
        elif diff_left == diff_closest:
            closest_index = min(closest_index, left)

    # Check the element at 'right' if it's within bounds
    if right >= 0:
        diff_right = abs(arr[right] - target)
        diff_closest = abs(arr[closest_index] - target)
        if diff_right < diff_closest:
            closest_index = right
        elif diff_right == diff_closest:
            closest_index = min(closest_index, right)

    return closest_index