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

简介: 题目 给你一个排好序的并且穿插有空字符串的字符串数组,写一个函数找到给定字符串的位置。 例子:在字符串数组 [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”,“”, “dad”, “”, “”] 中找到”ball”,返回下标4. 例子:在字符串数组 [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] 中找到”ballcar”,查找失败,返回-1. 解答 字符串数组已经是有序的了,所以,还是可以利用二分查找来找到指定的字符串。

题目

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

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

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

解答

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

代码如下:

#include <iostream>
using namespace std;

int search(string s[], int low, int high, string x){
    if(x == "") return -1; 
    while(low <= high){
        int mid = (low+high)>>1;
        int t = mid;
        while(s[t] == "" && t <= high) ++t;
        if(t > high) high = mid - 1;
        else{
            if(s[t] == x) return t;
            else if(s[t] < x) low = t + 1;
            else high = mid - 1; //or t-1
        }
    }
    return -1;
}
int main(){
    string s[13] = {
        "at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""
    };
    cout<<search(s, 0, 12, "ball")<<endl;
    return 0;
}

 

相关文章
|
7月前
|
存储 算法 C语言
找到数组位置
找到数组位置
|
4月前
|
存储 算法 索引
|
7月前
|
算法 测试技术 编译器
【算法 | 实验18】在字符矩阵中查找给定字符串的所有匹配项
题目描述 题目 在字符矩阵中查找给定字符串的所有匹配项 给定一个M×N字符矩阵,以及一个字符串S,找到在矩阵中所有可能的连续字符组成的S的次数。所谓的连续字符,是指一个字符可以和位于其上下左右,左上左下,右上右下8个方向的字符组成字符串。用回溯法求解。
102 1
|
6月前
leetcode题解:28.找出字符串中第一个匹配项的下标
leetcode题解:28.找出字符串中第一个匹配项的下标
26 0
题目:下列给定程序中函数fun的功能是:从p所指字符串中找出ASCII码值最大的字符,将其放在第一个位置上,并将该字符前的原字符向后顺序移动。
题目:下列给定程序中函数fun的功能是:从p所指字符串中找出ASCII码值最大的字符,将其放在第一个位置上,并将该字符前的原字符向后顺序移动。
定义一个长度为10的整型数组,循环输入10个整数。 然后将输入一个整数,查找此整数,找到后输出下标,没找到给出提示。
定义一个长度为10的整型数组,循环输入10个整数。 然后将输入一个整数,查找此整数,找到后输出下标,没找到给出提示。
219 0
在给定范围的数据中找到含有6的数据个数
在给定范围的数据中找到含有6的数据个数
|
C语言
查找某字符串出现的位置,并且输出该第一个字母所在的位
查找某字符串出现的位置,并且输出该第一个字母所在的位
135 0
查找某字符串出现的位置,并且输出该第一个字母所在的位
实现strrstr,找到子串最后的出现位置
实现strrstr,找到子串最后的出现位置
111 0
给定一个字符串,能否最多删除一段连续的一段使得剩下的为“2020”
给定一个字符串,能否最多删除一段连续的一段使得剩下的为“2020”
86 0