找出字符串

https://blog.csdn.net/LK274857347/article/details/71123086

有一个排过序的字符串数组，但是其中有插入了一些空字符串，请设计一个算法，找出给定字符串的位置。算法的查找部分的复杂度应该为log级别。
给定一个string数组str,同时给定数组大小n和需要查找的string x，请返回该串的位置(位置从零开始)。
测试样例：
["a","b","","c","","d"],6,"c"
返回：3

https://blog.csdn.net/LK274857347/article/details/71123086

  public int find(String[] str, int n, String toFindString) {

    if (str == null || n == 0)

      return -1;

    int low = 0, high = n - 1;

    while (low <= high) {

      int mid = (high - low) / 2 + low;

      if (str[mid] == "") {

        int index = mid;

        while (index >= low && str[index] == "") {

          index--;

        }

        if (index < low)

          low = mid + 1;

        else if (str[index].compareTo(toFindString) > 0)

          high = index - 1;

        else if (str[index] == toFindString)

          return index;

        else

          low = mid + 1;

      }

      if (str[mid].compareTo(toFindString) > 0)

        high = mid - 1;

      else if (str[mid].compareTo(toFindString) < 0)

        low = mid + 1;

      else if (str[mid] == toFindString)

        return mid;

    }

    return -1;

  }

  public int find2(String[] str, int n, String x) {

    // write code here

    if (str == null || n == 0)

      return -1;

//int length = str.length;

    int left = 0, right = n - 1;

    while (left <= right) {

      int mid = (right - left) / 2 + left;

      if (str[mid] == x)

        return mid;

      if (str[mid] == "") {

        int index = mid;

        while (index >= left && str[index] == "")

          index--;

        if (index < left)

          left = mid + 1;

        if (str[index] == x)

          return index;

        else if (str[index].compareTo(x) > 0)

          right = index - 1;

        else

          left = mid + 1;

      } // if(str[mid]=="")

      if (str[mid].compareTo(x) > 0)

        right = mid - 1;

      else if (str[mid].compareTo(x) < 0)

        left = mid + 1;

    } // while(left<=right){

    return -1;

  }

//该方法更加简洁，简单。

  public int find3(String[] str, int n, String x) {

    // write code here

    if (str == null || n == 0)

      return -1;

//int length = str.length;

    int left = 0;

    int right = n - 1;

    int mid;

    while (left <= right) {

      mid = (right + left) / 2;

      if (str[mid].equals("")) {

        mid--;

      } // if(str[mid]=="")

      if (str[mid].equals(x)) {// 牛客编译器使用==无法得到结果，显示时间超时。

        return mid;

      } else if (str[mid].compareTo(x) > 0) {

        right = mid - 1;

      } else {

        left = mid + 1;

      }

    } // while(left<=right){

    return -1;

  }

http://www.voidcn.com/article/p-pbkpujpb-bdv.html

    public int findString(String[] str, int n, String x) {
        // write code here
        int i =0,j=n-1;
        while(i<=j)
        {
            int mid = (i+j)/2;
            if(str[mid].equals(" "))
            {
                int index = mid;
                while(str[index].equals(" ")&&index>i)
                {
                    index--;
                }
                if(index==i)
                {
                    index = mid+1;
                    while(str[index].equals(" ")&&index<j)
                    {
                        index++;
                    }
                    
                }
                mid = index;
            }
            if(str[mid].equals(x))  return mid;
            else if(str[mid].compareTo(x)>0)    j = mid-1;
            else i = mid+1;


        }
        return -1;
    }

http://www.voidcn.com/article/p-welkqjqq-nx.html

这是一道二分查找 的变形题目。唯一的关注点就是当str[mid] == ""时的处理，此时仅通过str[mid]=""是无法判断目标是在mid的左边还是右边。所以，我们遍历mid左边的元素找到第一个不是空字符串的元素。
如果mid左边的所有元素都是空字符串，则去掉令s=mid+1；
否则
    找到第一个不是空字符串的元素下标为s1
    （1）如果str[s1]等于目标正好返回。
    （2）如果str[s1]大于目标，则说明目标在str[s1]左边，令e= s1- 1。
    （3）如果str[s1]小于目标，则说明目标在str[mid]右边，令s= mid + 1

class Finder {
public:
 int find(vector<string>& str, int s, int e, string& x)
 {
  if (s > e)return -1;
  int mid = (s + e) / 2;
  int index = -1;
  int s1 = mid;
  if (str[mid].empty())
  {
   while (s1 >s&& str[--s1].empty());
   
  }
  if (str[s1].compare(x)>0){
   index = find(str, s, s1 - 1, x);
  }
  else if (str[s1].compare(x) == 0){
   return s1;
  }
  else if (str[s1].compare(x) < 0) //mid左侧全部是空字符串或者左边第一个非空字符串比x小
  {
   index = find(str, mid+1, e, x);
  }
  
  return index;
 }

 int findString(vector<string> str, int n, string x) {
  // write code here
  int index = find(str, 0, n - 1, x);
  return index;
 }

答案和思路：因为含有“”，那么在到了mid的时候找一个和他最近的部位“”来代替他。这次是往左找到头了才开始往右找。优化的话两边都开始同时找。


    public int findString(String[] str, int n, String x) {
        // write code here
        if (null == str || n == 0) {
            return 0;
        }
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int keep = mid;
            while (mid >= left && str[mid].equals("")) {
                mid--;
            }
            if (mid < left) {
                mid = keep;
                while (mid <= right && str[mid].equals("")) {
                    mid++;
                    if (mid > right) {
                        return -1;
                    }
                }
            }
            if (str[mid].equals(x)) {
                return mid;
            }
            if (str[mid].compareTo(x) > 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }