Binary Search on string

Question

Implement a binary search algorithm to find the index of a target substring within a sorted array of strings. The function should take a sorted array of strings and a target string as input, returning the index of the target substring if found, or -1 if it is not present. Ensure your solution has a time complexity of O(log n).

Codemia · Accepted Answer

The task is to implement a binary search algorithm to find a target substring in a sorted array of strings. The key observation is that binary search is applicable here because the array is sorted and we can leverage the sorted nature to eliminate half of the search space in each step. The binary search algorithm operates on the principle of divide-and-conquer, making it efficient for searching in sorted datasets. We will be comparing the target substring against the mid-point of the current search range to determine if we need to search the left or right half of the array.

1. Initialize two pointers, 'left' at 0 and 'right' at the length of the array minus one.
2. While 'left' is less than or equal to 'right':
   - Calculate 'mid' as the average of 'left' and 'right'.
   - Compare the target substring with the string at 'mid'.
   - If they match, return 'mid'.
   - If the target is lexicographically less than the mid string, move the 'right' pointer to 'mid - 1'.
   - If the target is greater, move the 'left' pointer to 'mid + 1'.
3. If the loop ends without finding the target, return -1.

**Example**: Given the sorted array ['apple', 'banana', 'cherry', 'date'] and target 'cherry':
- Initially, left = 0, right = 3, mid = 1 (banana). Since 'cherry' > 'banana', we update left to 2.
- Now, mid = 2 (cherry). We found the target at index 2.

```python
def binary_search(strings, target):
    left, right = 0, len(strings) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if strings[mid] == target:
            return mid
        elif strings[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
```

The time complexity of this binary search implementation is O(log n), where n is the number of strings in the array. This is because each comparison reduces the search space by half. The space complexity is O(1) since we are only using a fixed number of variables for pointers and indices, independent of the input size.

1. **Empty Array**: If the input array is empty, we should return -1 as there are no elements to search.
2. **Target Not in Array**: If the target substring is not present in the array, we should also return -1.
3. **Target is the First or Last Element**: Ensure the function correctly identifies the target when it is at the boundaries of the array.
4. **Duplicate Strings**: The function should still return the correct index for duplicate entries of the target string, as long as one instance is found.

Binary Search on string

Capital One

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Capital One Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string