给定一个string数组str,其是由一个排过序的字符串数组插入了一些空字符串得到的,同时给定数组大小n和需要查找的string x,请用时间复杂度在log级别的算法返回该串的位置(位置从零开始)。
测试样例:
["a","b","","c","","d"],6,"c"
返回:3
import java.util.*; public class Finder { public int findString(String[] str, int n, String x) { if (n <=0) return -1; // write code here int l =0, r = str.length -1; while (l<=r) { int mid = l+ (r-l)/2; if (str[mid].length() ==0) { int index = mid; while ( index>=l && str[index].length()==0){ --index; } if (index < l) { //[l,mid ]一直都是空格,不用找了 l = mid +1; } else if(str[index] ==x) { return index; }else if(str[index].compareTo(x) >0) { r = mid -1; }else{ l = mid +1; } }else { if(str[mid].equals(x)) { return mid; }else if (str[mid].compareTo(x) >0) { //amid > x r = mid -1; }else{ l = mid +1; } } } return -9999; } }
import java.util.*; public class Finder { public int findString(String[] str, int n, String x) { // write code here int start=0; int end=str.length; while(start<=end){ int mid=(start+end)/2; if(str[mid].equals(x)){ return mid; } if(str[mid].compareTo(x)>0){ end=mid-1; }else if(str[mid].compareTo(x)<0){ start=mid+1; } } return -1; } }
import java.util.*; public class Finder { public int findString(String[] str, int n, String x) { int l=0,r=n-1; int lmid,rmid; while(l<=r){ lmid=(l+r)/2; rmid=(l+r)/2; while(str[lmid]=="") lmid--; while(str[rmid]=="") rmid++; if(str[lmid].equals(x)) return lmid; if(str[rmid].equals(x)) return rmid; if(str[lmid].compareTo(x)>0) r=lmid-1; else l=l=rmid+1; if(str[rmid].compareTo(x)<0) l=rmid+1; else r=lmid-1; } return -1; } }
public int findString(String[] str, int n, String x) { int low = 0; int high = str.length - 1; //等号不能漏!! while (low <= high) { int mid = low + (high - low) / 2; //如果为空,则对mid进行修正到最近的一个不是空的字符上去 if (str[mid].isEmpty()) { int left = mid - 1; int right = mid + 1; while (true) { if (left < low && right > high) { return -1; } else if (right <= high && !str[right].isEmpty()) { mid = right; break; } else if (left >= low && !str[left].isEmpty()) { mid = left; break; } right++; left--; } } if (str[mid].equals(x)) { return mid; } else if (str[mid].compareTo(x) < 0) {//搜索右半边 low = mid + 1; } else if (str[mid].compareTo(x) > 0) {//搜索左半边 high = mid - 1; } } return -1; }