Searching in Arrays & Strings -1
INTRODUCTION
No doubt if you code in Java, you must have encountered some algorithms to find some elements in an Array, whether its 1-D or 2-D or its a string. there are thousands of teachers on web who are making videos to make you understand these algorithms. As these are very important algorithms that you should know as a programmer. But many fellow coders who are putting efforts to learn coding get stuck when it comes to write a code for these algorithms.
but don't worry guys :) , once I also got stuck in these algorithms, So I thought to make a detailed post on this topic.
Searching in Arrays/Strings includes two types of methods to search :
1. Binary Search
2. Linear Search
Starting from Binary search
it's a very easy method to search for any element in an Array or String. In this method, you just have to iterate over whole array or String with the help of loops. If you have understood the working and logic of loops, then it will be very-very easy for you to implement binary search.
TIME COMPLEXITY
the time complexity in this type of search is
a) O(1) for best case
b) O(log n) for worst case
> In best case, it indicates that you have found your target element (which you need to search) in very first index of the array/string (i.e. 0)
> In worst case, it indicates that you have to iterate through whole array/string to find the target element, either you have found the element on very last index of array/string (i.e. n-1, where n is the size of array/string) or the element is not found though iteration is done though whole array/string.
CODE
import java.util.*;
public class binarysearch{
static int SrchinStr(String s, char target){
for(int i=0; i<s.length(); i++){
char IndexChar = s.charAt(i);
if(IndexChar == target){
return 1;
}
}
return -1;
}
static int binsrch2d(int[][] arr, int target){
for(int i=0; i<arr.length;i++){
for(int j=0;j<arr[i].length;j++){
int t = arr[i][j];
if(t == target){
return 1;
}
}
}
return -1;
}
static int binsrch(int[] arr, int target){
Arrays.sort(arr);
int start = 0;
int end = arr.length-1;
while(start <= end){
int mid = start + (end-start)/2;
if(target>arr[mid]){
start = mid+1;
}else if(target<arr[mid]){
end = mid-1;
}else{
return mid;
}
}
return -1;
}
public static void main(String args[]){
int[] arr1 = {11,10,23,2,4,66,67};
System.out.println(binsrch(arr1,44)); // -1
int[][] arr2 = {{1,2,3},{4,5,6},{7,8,9}};
System.out.println(binsrch2d(arr2,2)); // 1
String example = "CodinGates";
System.out.println(SrchinStr(example,'G')); // return and print 1 on console
System.out.println(SrchinStr(example,'g')); // return and print -1 on console
}
}
EXPLANATION
Let's go through the code step by step to understand what it does.
1. The code begins by defining a class called `binarysearch`.
2. Inside the class, there are three static methods: `SrchinStr`, `binsrch2d`, and `binsrch`, each serving different purposes.
3. `SrchinStr` is a method that performs a linear search for a character in a given string and returns its index if found or -1 if not found.
- `SrchinStr` takes two parameters: a string `s` and a character `target`.
- It iterates through the characters of the input string `s` using a `for` loop.
- For each character, it checks if it matches the `target` character.
- If a match is found, it immediately returns 1, indicating the character is present in the string.
- If the loop completes without finding the `target` character, it returns -1, indicating that the character is not in the string.
4. `binsrch2d` is a method that performs a linear search for a target integer in a two-dimensional array and returns 1 if found or -1 if not found.
- `binsrch2d` takes two parameters: a 2D integer array `arr` and an integer `target`.
- It uses two nested `for` loops to iterate through all the elements of the 2D array.
- For each element `t`, it checks if it matches the `target`.
- If a match is found, it immediately returns 1, indicating the target integer is present in the array.
- If the loops complete without finding the `target` integer, it returns -1, indicating that the integer is not in the array.
5. `binsrch` is a method that performs a binary search for a target integer in a sorted integer array and returns the index of the target if found or -1 if not found.
- `binsrch` takes two parameters: an integer array `arr` and an integer `target`.
- It first sorts the input array using `Arrays.sort(arr)` to ensure binary search can be performed.
- It initializes two pointers `start` and `end` representing the start and end of the search range, respectively.
- It uses a `while` loop to continue the search until `start` becomes greater than `end`, indicating the search range is invalid.
- Inside the loop, it calculates the `mid` index and compares the `target` with the element at the `mid` index.
- If the `target` is greater than the element at `mid`, it updates `start` to `mid + 1` to search in the right half of the array.
- If the `target` is less than the element at `mid`, it updates `end` to `mid - 1` to search in the left half of the array.
- If the `target` is equal to the element at `mid`, it means the target is found, and it returns the `mid` index.
- If the loop completes without finding the `target`, it returns -1, indicating that the `target` is not in the array.
6. In the `main` method, the code demonstrates the usage of these three methods:
- It creates an integer array `arr1` and a 2D integer array `arr2`.
- It calls `binsrch` to search for the integer 44 in `arr1`, which should return -1 since 44 is not present in the array.
- It calls `binsrch2d` to search for the integer 2 in `arr2`, which should return 1 since 2 is present in the array.
- It calls `SrchinStr` to search for the character 'G' in the string "CodinGates", which should return 1 since 'G' is present in the string.
- It calls `SrchinStr` to search for the character 'g' in the same string, which should return -1 since 'g' (lowercase) is not present in the string.
HAPPY CODING :)
Post a Comment