9.5 写一个函数找到给定字符串的位置

题目

给你一个排好序的并且穿插有空字符串的字符串数组,写一个函数找到给定字符串的位置。

例子:在字符串数组 [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”,“”, “dad”, “”, “”] 中找到"ball",返回下标4.

例子:在字符串数组 [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] 中找到"ballcar",查找失败,返回-1.

解答

字符串数组已经是有序的了,所以,还是可以利用二分查找来找到指定的字符串。 当然了,由于数组中有空字符串,因此还要加些额外的处理,否则无法对比大小。 我们可以这样来处理,如果要对比的那个元素为空字符串,就一直向右移动, 直到字符串不为空或是位置已经超出了high下标。如果位置已经超出high下标, 就在[low, mid-1]这一段查找;如果没有超出high下标,那就和要查找的x进行对比。 相等时返回下标,不等时再根据比较出的大小决定到哪一半去查找。

代码如下:

 【原文参考】

剖析:

Use  ordinary  binary  search,  but  when  you  hit  an  empty  string,  advance  to  the  next  non-empty string; if there is no next non-empty string, search the left half

 

文/Hawstein

0 Likes

你目前的身份是游客,评论请输入昵称和电邮!