首页 > 其他 > 详细

CC150 9.5

时间:2014-12-05 19:47:44      阅读:250      评论:0      收藏:0      [点我收藏+]

9.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string. Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4 Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1


Normal O(n).


But A better one?


Let‘s binary search.

int search (String[] a, String s)
{
  return search(a, 0, a.length - 1, s);
}

int search (String[] a, int l, int h, String s)
{
  if (l > h)
    return -1;
  
  int m = (l + h) / 2;
  
  // Move to first non empty string
  int nm = m;
  while (a[nm].isEmpty())
  {
   nm ++;
   if (nm  > h) return -1;
  }
  
  if (a[nm] == s)
    return nm;
  else if (a[nm] > s)
    return search(a, l, m - 1, s);
  else 
    return search(a, nm + 1, h, s);
}


CC150 9.5

原文:http://7371901.blog.51cto.com/7361901/1586519

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!