10.05. Sparse Array Search

s

class Solution:
    def findString(self, words: List[str], s: str) -> int:
        left, right = 0, len(words) - 1
        while left < right:
            mid = (left + right) >> 1
            while left < mid and words[mid] == '':
                mid -= 1
            if s <= words[mid]:
                right = mid
            else:
                left = mid + 1
        return -1 if words[left] != s else left

class Solution {
    public int findString(String[] words, String s) {
        int left = 0, right = words.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            while (left < mid && "".equals(words[mid])) {
                --mid;
            }
            if (s.compareTo(words[mid]) <= 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return s.equals(words[left]) ? left : -1;
    }
}

class Solution {
public:
    int findString(vector<string>& words, string s) {
        int left = 0, right = words.size() - 1;
        while (left < right)
        {
            int mid = left + right >> 1;
            while (left < mid && words[mid] == "") --mid;
            if (s <= words[mid]) right = mid;
            else left = mid + 1;
        }
        return words[left] == s ? left : -1;
    }
};

func findString(words []string, s string) int {
	left, right := 0, len(words)-1
	for left < right {
		mid := (left + right) >> 1
		for left < mid && words[mid] == "" {
			mid--
		}
		if s <= words[mid] {
			right = mid
		} else {
			left = mid + 1
		}
	}
	if words[left] == s {
		return left
	}
	return -1
}