More
Searching Algorithms In Java
What is a Search Algorithm?
Any algorithm that is able to solve the search issue, which is to find information that is discretely or continuously valued and stored in a data structure or computed in the search space of a problem domain.
Searching algorithms are made to look up or retrieve a stored element from any data structure.
In the search space, they look for a target (key), as for example.
- everyone in the class.
- any of the digits in a provided list.
These operations result in either Success or Failure, or "Success" when the target is located and "Failure" when it is not.
Based on the different search operations that these algorithms may perform, they are primarily divided into two types. They are, too.
Types of Searching Algorithms
- Linear Search
- Binary Search
- Jump Search
- Interpolation Search
- Exponential Search
- Sublist Search (Search a linked list in another list)
- Fibonacci Search
- The Ubiquitous Binary Search
We'll focus on linear search and binary search in this blog. so we will cover those left outs in another blog.
- Linear Search
A technique for locating an element inside a list is a linear search, also known as a sequential search. The elements of the list are successively checked by this kind of searching algorithm until a match is made or the whole list has been searched.
In worst-case linear time, a linear search performs at most n comparisons, where n is the length of the list.
If each element is equally likely to be searched, then linear search has an average case of n+1/2 comparisons, but the average case can be affected if the search probabilities for each element vary.
Since alternative search algorithms and schemes, including the binary search algorithm and hash tables, provide much quicker searching for anything but short lists, linear search is rarely useful.
A flowchart showing the linear search
Of all search algorithms, a linear search method is regarded as the most fundamental. The best search algorithms are said to use the binary search strategy.
The number of times the worst-case search key comparisons are performed is used to how effective a search algorithm is. O(n), where n is the total number of comparisons performed, is the notation that search algorithms use.
It provides a general understanding of the asymptotic upper limit of the algorithm's execution time with regard to a specified condition.
Let's use an example to better understand this:
Write a method to search for a certain member in an array of n items called arr[].
Examples-
| Input : arr[] = {10, 20, 80, 30, 40, 50, 110, 90, 0, 70}; x = 110; Output : 6 Element x is present at index 6 Input : arr[] = {10, 20, 80, 30, 60, 50, 120, 140, 130, 170}; x = 175; Output : -1 Element x is not present in arr[]. |
Linear search is a straightforward strategy, i.e.
Beginning with the element of arr[] on the left and sequentially compare each element in arr with x.
- If x matches with an element, return the index.
- If x doesn’t match with any of elements, return -1.
class Search{ //linearSearch public int linearSearch(int arr[], int size, int key){ int i; for(i=0; i<size; i++){ //For loop for comparing every element present in the list if(arr[i] == key){ //If array element and key element same it will return 1; return 1; } } //This returns 0 if an element is not found in the array list. return 0; } } //Main Class public class LinearSearch { public static void main(String[] args) { //Creating object Search obj = new Search(); // Searching key or element in 500 int Key = 500; //Array containing an element int arr[] = {10,20,30,40,50,60}; //Passing Key, arr, arr.length to linear Search method() if(obj.linearSearch(arr,arr.length,Key) == 1) { //If key is found it return value 1 //If key is found then it print This statement System.out.println("Element is present in an array"); } else{ //If key is not found return value is 0. System.out.println("Element is not present in an array"); } } } |
| OUTPUT : |
| Element is not present in an array |
The time complexity of above algorithm is O(n).
The time Space of above algorithm is O(1).
Binary Search
To find a specific value inside a sorted array, this form of searching methods is utilised. Because of its quicker search speed, the binary search algorithm, which operates on the divide and conquer principle, is regarded as the best searching algorithm ( Provided the data is in sorted form).
- A binary search is often referred to as a logarithmic search or a half-interval search.
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree. There must be no duplicate nodes
The array's centre is initially searched, then the first lower or higher half of the sequence. If the median value is less than the desired value, the search must go up the array; otherwise, it must scan the descending part of the array.
The node-based binary tree data structure known as the "Binary Search Tree" includes the following characteristics:
A binary search is a quick and efficient method of finding a specific target value from a set of ordered items. By starting in the middle of the sorted list, it can effectively cut the search space in half by determining whether to ascend or descend the list based on the median value compared to the target value.
For example, with a target value of 8 and a search space of 1 through 11:
- The median/middle value is found and the pointer is set there, which in this case is 6.
- The target of 8 is compared to 6. Since 6 is smaller than 8, the target must be in the higher half.
- The pointer is moved to the next value (7) and compared to the target. It is smaller, therefore the pointer moves to the next higher value.
- The pointer is now on 8. Comparing this to the target, it is an exact match, therefore the target has been found.
The target only needed to be compared to 3 values when using binary search. In contrast to doing a linear search, it would have had to compare the target to eight values, starting with the very first value and working its way up.
A binary search is possible only with an ordered set of data, if the data is randomly arranged, then a linear search would yield results.
Example: Binary Search
class BinaryS{ //Method For searching Element is fount or not. public int binarySearch(int arr[], int start, int end, int key){ //mid is used to find an middle element; int mid; //In before starting loop start = 0 and end = 9; //The conditional is true 0<=9 //Program will enter to While loop while(start <= end){ //start = 0 //end = 9; mid = (start + end) / 2; //Finding an middel element if(arr[mid] == key){ //Key and middel element is Found Return 1 return 1; } //If the above condition is wrong then this statment is execute this condition if(arr[mid] < key ){ //The mid gratter then key //Example : //middle = 50; //key = 70 //Here key is grateer then middle element start = mid+1; //Now start index become middle + 1 that is = (0+9)/2 = 4; //start = 4+1 = 5; } //If End > End the condition statment will become true //Example: // 9 > 9 is wrong //Statment will not execute //Example 2: // 9>10 is True //statment will execute //control will go to below if condition body if(end > end){ //It will return 0. return 0; } //Above both statment is wrong then this part will execute else{ // end = mid + 1; end = mid + 1; } } return 0; }} public class BinarySearch { public static void main(String[] args) { //array int arr[] = {10,20,30,40,50,60,70,80,90}; //Array Length int end = arr.length; //Index start with int start = 0; //Key to search an element int key = 90; //Creating an object. BinaryS obj = new BinaryS(); //Calling Function //Passing paramenter to Function if(obj.binarySearch(arr, start, end, key) == 1){ //Return 1 if Serch Element is fount System.out.println("Element is found"); } else{ //Return 0 if search Element is not Fount System.out.println("Element is Not found"); } } } |
| OUTPUT : Element is found |
The time complexity of above algorithm is O(log n).
The time space of the above algorithm is O(1).
