给定一个有序字符串数组,其中字符串两边可能会插入若干个空串。实现一个方法找到给定串的下标。
例子:
输入:[ "at", "", "", "", "ball", "", "", "car", "", "", "dad", "", "" ],"ball"输出:4
输入:[ "at", "", "", "", "ball", "", "", "car", "", "", "dad", "", "" ],"ballcar"输出:-1
思路:
用二分查找的思想,但要针对空串做些额外的处理。用left、mid、right分表表示数组的左、中、右。如果right对应的串为空串,继续向前扫描直到找到第一个非空串,然后求mid的值,如果mid对应的串为空串,继续向右扫描直到找到......
阅读全文