在有空字符串的有序字符串数组中查找

缺乏、安全感 2022-12-11 05:25 113阅读 0赞

#### 题目： ####

有一个排序后的字符串数组，其中散布着一些空字符串，编写一个方法，找出给定字符串（肯定不是空字符串）的索引。

#### 分析： ####

这道题也是用二分查找，注意在选取mid时，如果为空字符串，mid++即可。

#### 代码实现： ####

public class _07在有空字符串的有序字符串数组中查找 { 
    	public static void main(String[] args) { 
    		String[]arr = { "a","","ac","","ad","b","","ba"};
    		int res = indexOf(arr,"b");
    		System.out.println(res);
    	}
    
    	private static int indexOf(String[] arr, String p) { 
    		int begin = 0;
    		int end = arr.length-1;
    		while(begin<=end) { 
    			int indexOfMid = (begin+end)/2;
    			while(arr[indexOfMid].equals(""))
    				indexOfMid++;
    			//千万要注意
    			if (indexOfMid>end) { 
    				return -1;
    			}
    			//java中的compareTo方法，返回参与比较的前后两个字符串的asc码的差值
    			//如果两个字符串首字母不同，则该方法返回首字母的asc码的差值；
    			//如果首字符相同，则比较下一个字符，直到有不同的为止，返回该不同的字符的asc码差值
    			//如果两个字符串不一样长，但参与比较的字符又完全一样，则返回两个字符串的长度差值
    			if (arr[indexOfMid].compareTo(p)>0) { 
    				end=indexOfMid-1;
    			}else if (arr[indexOfMid].compareTo(p)<0) { 
    				begin=indexOfMid+1;
    			}else { 
    				return indexOfMid;
    			}
    		}
    		return -1;
    	}
    }

#### 运行结果： ####

![在这里插入图片描述][20200928174110375.png_pic_center]

[20200928174110375.png_pic_center]: /images/20221123/f7a62fdaf40d4b61b8a339d164edb3f1.png