Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Sparse Search

problem

Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string.

how to solve

If it were not for the empty strings, we could simply use binary search. With empty strings interspersed, we can implement a simple modification of binary search. We just find closest non-empty string if mid is empty.

code

Remove all ads