有个排序后的字符串数组,其中散布着一些空字符串,找出给定字符串的位置
有个排序后的字符串数组,其中散布着一些空字符串,找出给定字符串的位置
一贱书生 发表于12个月前
有个排序后的字符串数组,其中散布着一些空字符串,找出给定字符串的位置
  • 发表于 12个月前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 学生专属云服务套餐 10元起购>>>   

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

/**

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

 */
[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. }
共有 人打赏支持
粉丝 14
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: