Search in an array of strings where non | C ++ program to find location of a str in an array of strings which is sorted and has empty strings between strings . ; Compare two string equals are not ; Main function to find string location ; Move mid to the middle ; If mid is empty , find closest non - empty string ; If mid is empty , search in both sides of mid and find the closest non - empty string , and set mid accordingly . ; If str is found at mid ; If str is greater than mid ; If str is smaller than mid ; Driver Code ; Input arr of Strings . ; input Search String
#include <bits/stdc++.h> NEW_LINE using namespace std ; int compareStrings ( string str1 , string str2 ) { int i = 0 ; while ( str1 [ i ] == str2 [ i ] && str1 [ i ] != ' \0' ) i ++ ; if ( str1 [ i ] > str2 [ i ] ) return -1 ; return ( str1 [ i ] < str2 [ i ] ) ; } int searchStr ( string arr [ ] , string str , int first , int last ) { if ( first > last ) return -1 ; int mid = ( last + first ) / 2 ; if ( arr [ mid ] . empty ( ) ) { int left = mid - 1 ; int right = mid + 1 ; while ( true ) { if ( left < first && right > last ) return -1 ; if ( right <= last && ! arr [ right ] . empty ( ) ) { mid = right ; break ; } if ( left >= first && ! arr [ left ] . empty ( ) ) { mid = left ; break ; } right ++ ; left -- ; } } if ( compareStrings ( str , arr [ mid ] ) == 0 ) return mid ; if ( compareStrings ( str , arr [ mid ] ) < 0 ) return searchStr ( arr , str , mid + 1 , last ) ; return searchStr ( arr , str , first , mid - 1 ) ; } int main ( ) { string arr [ ] = { " for " , " " , " " , " " , " geeks " , " ide " , " " , " practice " , " " , " " , " quiz " , " " , " " } ; string str = " quiz " ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << searchStr ( arr , str , 0 , n - 1 ) ; return 0 ; }