题目.png

题意：稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。

解法1：
1.暴力解法，遍历string数组，找到对应的字符串

解法2：
1.二分查找，按照二分查找的思想，编写代码即可
2.二分查找过程中，处理空字符串，如果遇到空字符串，则收缩右边界（right--），但是在收缩之前，先判断一下right的值是否为s，如果是则直接返回

解题遇到的问题

1.equals与==的区别
1）基本数据类型，两者一样，对比的都是值，可以查看基本数据类型的equals实现，里面也是通过==来操作的，但是注意boolean、int有值范围默认存储对象
2）引用数据类型，==对比的是地址，两个对象地址是否一样，equals对比的是内容

2.String的对比compareTo内部如何实现的？
查看源码，是通过转换为字节数据，for循环对比每个字节实现的

后续需要总结学习的知识点

无

##解法1
class Solution {
    public int findString(String[] words, String s) {
        int res = -1;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(s)) {
                res = i;
                break;
            }
        }
        return res;
    }
}

##解法2
class Solution {
    public int findString(String[] words, String s) {
        int res = binarySearch(words, 0, words.length - 1, s);
        return res;
    }

    private int binarySearch(String[] words, int i, int j, String s) {
        while (i <= j) {
            int mid = (i + j) / 2;
            if (words[mid].equals("")) {
                if (words[j].equals(s)) {
                    return j;
                } else {
                    j--;
                }
            } else {
                if (words[mid].equals(s)) {
                    return mid;
                } else if (words[mid].compareTo(s) > 0) {
                    j = mid - 1;
                } else {
                    i = mid + 1;
                }
            }
        }
        return -1;
    }
}