Problem

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string. Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4 Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

Solution The worst we can do is O(n) where we just do a linear search. I tried to do better in the sense that we do a binary search, however if we encounter “”, we have to exam both sides. In this way, worst case we still do a O(n) search but in average, it’s better off.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public static int **findLocation**(String[] array, int i, int j, String str) {
 int mid;
 while (i <= j) {
 mid = (i + j) / 2;
 if (array[mid].equals("")) {
 int leftIndex = **findLocation**(array, i, mid - 1, str);
 if (leftIndex == -1)
 return **findLocation**(array, mid + 1, j, str);
 else
 return leftIndex;
 } else {
 if ([str.compareTo(array](http://str.compareTo(array)[mid]) == 0)
 return mid;
 if ([str.compareTo(array](http://str.compareTo(array)[mid]) < 0)
 j = mid - 1;
 if ([str.compareTo(array](http://str.compareTo(array)[mid]) > 0)

## Problem

Given a sorted array of strings, which may contain empty strings (`""`), find the index of a given target string.

### Examples

#### Example 1
```d
Input:
    array = ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""]
    target = "ball"
Output:
    4
Explanation:
    The string "ball" is found at index 4.

Example 2

1
2
3
4
5
6
7

Input:
    array = ["at", "", "", "", "", "ball", "car", "", "", "dad", "", ""]
    target = "ballcar"
Output:
    -1
Explanation:
    The string "ballcar" is not present in the array, so return -1.

Constraints

  • The array is sorted lexicographically.
  • The array may contain empty strings interspersed between non-empty strings.
  • The target string is a non-empty string.

Solution

Method 1 – Modified Binary Search (Divide and Conquer)

Intuition

Binary search is efficient for sorted arrays, but empty strings break direct comparison. The key idea is: when we hit an empty string, we search both sides to find the nearest non-empty string for comparison, then continue binary search as usual.

Approach

  1. Start with two pointers, left and right, at the bounds of the array.
  2. While left <= right:
    1. Compute mid = (left + right) // 2.
    2. If array[mid] is empty, expand outwards from mid to find the closest non-empty string.
    3. Compare the non-empty string at mid with the target: - If equal, return mid. - If less, move left to mid + 1. - If greater, move right to mid - 1.
  3. If not found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
 public:
        int SearchString(const std::vector<std::string>& arr, const std::string& target) {
                int left = 0;
                int right = arr.size() - 1;
                while (left <= right) {
                        int mid = left + (right - left) / 2;
                        int orig_mid = mid;
                        // Find closest non-empty string
                        while (mid >= left && arr[mid] == "") {
                                --mid;
                        }
                        if (mid < left) {
                                mid = orig_mid + 1;
                                while (mid <= right && arr[mid] == "") {
                                        ++mid;
                                }
                                if (mid > right) {
                                        return -1;
                                }
                        }
                        if (arr[mid] == target) {
                                return mid;
                        }
                        if (arr[mid] < target) {
                                left = orig_mid + 1;
                        } else {
                                right = mid - 1;
                        }
                }
                return -1;
        }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func SearchString(arr []string, target string) int {
        left, right := 0, len(arr)-1
        for left <= right {
                mid := left + (right-left)/2
                origMid := mid
                for mid >= left && arr[mid] == "" {
                        mid--
                }
                if mid < left {
                        mid = origMid + 1
                        for mid <= right && arr[mid] == "" {
                                mid++
                        }
                        if mid > right {
                                return -1
                        }
                }
                if arr[mid] == target {
                        return mid
                }
                if arr[mid] < target {
                        left = origMid + 1
                } else {
                        right = mid - 1
                }
        }
        return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Solution {
        public int searchString(String[] arr, String target) {
                int left = 0;
                int right = arr.length - 1;
                while (left <= right) {
                        int mid = left + (right - left) / 2;
                        int origMid = mid;
                        while (mid >= left && arr[mid].isEmpty()) {
                                mid--;
                        }
                        if (mid < left) {
                                mid = origMid + 1;
                                while (mid <= right && arr[mid].isEmpty()) {
                                        mid++;
                                }
                                if (mid > right) {
                                        return -1;
                                }
                        }
                        if (arr[mid].equals(target)) {
                                return mid;
                        }
                        if (arr[mid].compareTo(target) < 0) {
                                left = origMid + 1;
                        } else {
                                right = mid - 1;
                        }
                }
                return -1;
        }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
        fun searchString(arr: List<String>, target: String): Int {
                var left = 0
                var right = arr.size - 1
                while (left <= right) {
                        var mid = left + (right - left) / 2
                        val origMid = mid
                        while (mid >= left && arr[mid].isEmpty()) {
                                mid--
                        }
                        if (mid < left) {
                                mid = origMid + 1
                                while (mid <= right && arr[mid].isEmpty()) {
                                        mid++
                                }
                                if (mid > right) {
                                        return -1
                                }
                        }
                        if (arr[mid] == target) {
                                return mid
                        }
                        if (arr[mid] < target) {
                                left = origMid + 1
                        } else {
                                right = mid - 1
                        }
                }
                return -1
        }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from typing import List

class Solution:
    def search_string(self, arr: List[str], target: str) -> int:
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = left + (right - left) // 2
            orig_mid = mid
            while mid >= left and arr[mid] == "":
                mid -= 1
            if mid < left:
                mid = orig_mid + 1
                while mid <= right and arr[mid] == "":
                    mid += 1
                if mid > right:
                    return -1
            if arr[mid] == target:
                return mid
            if arr[mid] < target:
                left = orig_mid + 1
            else:
                right = mid - 1
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
        pub fn search_string(arr: &[String], target: &str) -> i32 {
                let (mut left, mut right) = (0, arr.len() as i32 - 1);
                while left <= right {
                        let mut mid = left + (right - left) / 2;
                        let orig_mid = mid;
                        while mid >= left && arr[mid as usize] == "" {
                                mid -= 1;
                        }
                        if mid < left {
                                mid = orig_mid + 1;
                                while mid <= right && arr[mid as usize] == "" {
                                        mid += 1;
                                }
                                if mid > right {
                                        return -1;
                                }
                        }
                        if arr[mid as usize] == target {
                                return mid as i32;
                        }
                        if arr[mid as usize] < target {
                                left = orig_mid + 1;
                        } else {
                                right = mid - 1;
                        }
                }
                -1
        }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
        searchString(arr: string[], target: string): number {
                let left = 0;
                let right = arr.length - 1;
                while (left <= right) {
                        let mid = left + Math.floor((right - left) / 2);
                        const origMid = mid;
                        while (mid >= left && arr[mid] === "") {
                                mid--;
                        }
                        if (mid < left) {
                                mid = origMid + 1;
                                while (mid <= right && arr[mid] === "") {
                                        mid++;
                                }
                                if (mid > right) {
                                        return -1;
                                }
                        }
                        if (arr[mid] === target) {
                                return mid;
                        }
                        if (arr[mid] < target) {
                                left = origMid + 1;
                        } else {
                                right = mid - 1;
                        }
                }
                return -1;
        }
}

Complexity

  • ⏰ Time complexity: O(n) in the worst case, because if the array is mostly empty strings, we may have to scan linearly to find non-empty strings. In the average case, binary search dominates, so it’s closer to O(log n).
  • 🧺 Space complexity: O(1), since only a constant amount of extra space is used for pointers and indices.