Searching in a sorted array of strings with empty strings
MediumUpdated: Sep 13, 2025
Problem
Given a sorted array of strings, which may contain empty strings (""), find the index of a given target string.
OR
Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
Examples
Example 1
Input:
array = ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""]
target = "ball"
Output:
4
Explanation:
The string "ball" is found at index 4.
Example 2
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 - Linear Search
The worst we can do is O(n) where we just do a linear search, but given string is sorted, we can use binary search, but some modification will be required.
Method 2 – 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
- Start with two pointers,
leftandright, at the bounds of the array. - While
left <= right:- Compute
mid = (left + right) // 2. - If
array[mid]is empty, expand outwards frommidto find the closest non-empty string. - Compare the non-empty string at
midwith the target: - If equal, returnmid. - If less, movelefttomid + 1. - If greater, moverighttomid - 1.
- Compute
- If not found, return -1.
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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
}
}
TypeScript
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 toO(log n). - 🧺 Space complexity:
O(1), since only a constant amount of extra space is used for pointers and indices.