有个排序后的字符串数组,其中散布着一些空字符串,找出给定字符串的位置

原创
2016/11/24 08:45
阅读数 314

版权声明:本文为博主原创文章,未经博主允许不得转载。

/**

 * 功能:有个排序后的字符串数组,其中散布着一些空字符串,找出给定字符串的位置。

 */
[java] view plain copy

 

  1. /** 
  2.  * 思路:对二分查找法做修改,与mid比较的地方,如果mid为空字符串,则将mid换到离它最近的非空字符串的位置。 
  3.  * @param strings 
  4.  * @param str 
  5.  * @return 
  6.  */  
  7. public static int search(String[] strings,String str){  
  8.     if(strings==null||str==null||str=="")  
  9.         return -1;  
  10.     return searchStr(strings,str,0,strings.length);  
  11. }  
  12.   
  13. public static int searchStr(String[] strings,String str,int first,int last){  
  14.     if(first>last)  
  15.         return -1;  
  16.       
  17.     int mid=(first+last)/2;  
  18.     //若mid为空字符串,找出离它最近的非空字符串  
  19.     if(strings[mid].isEmpty()){  
  20.         int left=mid-1;  
  21.         int right=mid+1;  
  22.         while(true){  
  23.             if(left<first&&right>last)  
  24.                 return -1;  
  25.             else if(right<last&&!strings[right].isEmpty()){  
  26.                 mid=right;  
  27.                 break;  
  28.             }else if(left>first&&!strings[left].isEmpty()){  
  29.                 mid=left;  
  30.                 break;  
  31.             }  
  32.             left--;  
  33.             right++;  
  34.         }  
  35.     }  
  36.       
  37.     if(str.equals(strings[mid]))  
  38.         return mid;  
  39.     else if(strings[mid].compareTo(str)<0)  
  40.         return searchStr(strings, str, mid+1, last);//搜索右半边  
  41.     else  
  42.         return searchStr(strings, str, first, mid-1);//搜索左半边          
  43. }
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部