Given a sorted array of Strings arr and a String x, find an index of x if it is present in the array, using Binary Search
Examples:
Input: arr[] = {“contribute”, “neveropen”, “ide”, “practice”}, x = “ide”
Output: 2
Explanation: The String x is present at index 2.Input : arr[] = {“contribute”, “neveropen”, “ide”, “practice”}, x = “zz”
Output : -1
Explanation: The String “zz” is not present.
Approach to Find a String in a given Array of Strings:
The idea is to apply Binary Search on the given Array of Strings.
Illustrations:
Suppose the array of string is arr[] = {“contribute”, “neveropen”, “ide”, “practice”}, and the key string to find is x = “ide”.
Now the above approach will be performed like this:
1st iteration:
- Low = 0, High = 4, Hence Mid = 2
- Element at index 2 = “ide”, which is equal to the key string x
- Therefore, x is found.
Below are the steps on how to Find a String in a given Array of Strings using Binary Search:
- Find the Middle element of the Array of the String, and compare it with the String x.
- If the key is found, return the index of the middle.
- Else check if the mid string is smaller or larger than the key string x.
- If it is smaller, reduce the search space to the lower half
- If it is larger, reduce the search space to greater than half
- Repeat the above steps till the key string x is found, or no more search space is left to search.
Below is the implementation of the above approach:
C++
// C++ program to implement // Binary Search for strings #include <bits/stdc++.h> using namespace std; // Returns index of x if it is present // in arr[], else return -1 int binarySearch(string arr[], string x, int n) { int l = 0; int r = n - 1; // Loop to implement Binary Search while (l <= r) { // Calculatiing mid int m = l + (r - l) / 2; // Some random value assigned // as 0 belongs to index int res = -1000; if (x == (arr[m])) res = 0; // Check if x is present at mid if (res == 0) return m; // If x greater, ignore left half if (x > (arr[m])) l = m + 1; // If x is smaller, ignore right half else r = m - 1; } return -1; } // Driver code int main() { string arr[] = { "contribute", "neveropen", "ide", "practice" }; string x = "ide"; int n = 4; int result = binarySearch(arr, x, n); if (result == -1) cout << ("Element not present"); else cout << ("Element found at index ") << result; } // This code is contributed by // Shashank_Sharma |
Java
// Java program to implement Binary Search for strings class GFG { // Returns index of x if it is present in arr[], // else return -1 static int binarySearch(String[] arr, String x) { int l = 0, r = arr.length - 1; // Loop to implement Binary Search while (l <= r) { // Calculatiing mid int m = l + (r - l) / 2; int res = x.compareTo(arr[m]); // Check if x is present at mid if (res == 0) return m; // If x greater, ignore left half if (res > 0) l = m + 1; // If x is smaller, ignore right half else r = m - 1; } return -1; } // Driver method to test above public static void main(String[] args) { String[] arr = { "contribute", "neveropen", "ide", "practice" }; String x = "ide"; int result = binarySearch(arr, x); if (result == -1) System.out.println("Element not present"); else System.out.println("Element found at " + "index " + result); } } |
Python3
# Python3 program to implement Binary # Search for strings # Returns index of x if it is present # in arr[], else return -1 def binarySearch(arr, x): l = 0 r = len(arr) # Loop to implement Binary Search while (l <= r): # Calculatiing mid m = l + ((r - l) // 2) res = (x == arr[m]) # Check if x is present at mid if (res == 0): return m - 1 # If x greater, ignore left half if (res > 0): l = m + 1 # If x is smaller, ignore right half else: r = m - 1 return -1 # Driver Code if __name__ == "__main__": arr = ["contribute", "neveropen", "ide", "practice"] x = "ide" result = binarySearch(arr, x) if (result == -1): print("Element not present") else: print("Element found at index", result) # This code is contributed by ita_c |
C#
// C# program to implement Binary Search for strings using System; class GFG { // Returns index of x if it is present in arr[], // else return -1 static int binarySearch(String[] arr, String x) { int l = 0, r = arr.Length - 1; // Loop to implement Binary Search while (l <= r) { // Calculatiing mid int m = l + (r - l) / 2; int res = x.CompareTo(arr[m]); // Check if x is present at mid if (res == 0) return m; // If x greater, ignore left half if (res > 0) l = m + 1; // If x is smaller, ignore right half else r = m - 1; } return -1; } // Driver method to test above public static void Main(String[] args) { String[] arr = { "contribute", "neveropen", "ide", "practice" }; String x = "ide"; int result = binarySearch(arr, x); if (result == -1) Console.WriteLine("Element not present"); else Console.WriteLine("Element found at " + "index " + result); } // This code is contributed by Ryuga } |
PHP
<?php // PHP program to implement Binary // Search for strings // Returns index of x if it is present // in arr[], else return -1 function binarySearch($arr, $x) { $l = 0; $r = count($arr); // Loop to implement Binary Search while ($l <= $r) { // Calculatiing mid $m = $l + (int)(($r - $l) / 2); $res = strcmp($x, $arr[$m]); // Check if x is present at mid if ($res == 0) return $m; // If x greater, ignore left half if ($res > 0) $l = $m + 1; // If x is smaller, ignore right half else $r = $m - 1; } return -1; } // Driver Code $arr = array("contribute", "neveropen", "ide", "practice"); $x = "ide"; $result = binarySearch($arr, $x); if ($result == -1) print("Element not present"); else print("Element found at index " . $result); // This code is contributed by mits ?> |
Javascript
// Javascript program to implement Binary Search for strings // Returns index of x if it is present in arr[], // else return -1 function binarySearch(arr, x) { let l = 0, r = arr.length - 1; // Loop to implement Binary Search while (l <= r) { // Calculatiing mid let m = l + Math.floor((r - l) / 2); let res = x.localeCompare(arr[m]); // Check if x is present at mid if (res == 0) return m; // If x greater, ignore left half if (res > 0) l = m + 1; // If x is smaller, ignore right half else r = m - 1; } return -1; } // Driver method to test above let arr = ["contribute", "neveropen", "ide", "practice"]; let x = "ide"; let result = binarySearch(arr, x); if (result == -1) console.log("Element not present"); else console.log("Element found at " + "index " + result); // This code is contributed by rag2127 |
Output
Element found at index 2
Time Complexity: O(log(n) * len), where n = no. of string in arr & len = max length of the string for comparing two strings we need O(len) time
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
