Linear Search:
A navie search techniques and keep comparing element till matches found. It basically compares the element you are searching for with every element in the array. It keeps on comparing till the algorithm finds the required element or it reaches the end of the array to conclude that the element does not exist in the array.
Brute-force searching :
Brute-force searching is also known as exhaustive searching and simply means to check all possible configurations for a given problem. It is easy to implement and will most definitely find the solution but it is quite time-consuming.
For example :
If you have a problem set in a countable space (chess moves are countable, passwords are countable, continuous stuff is uncountable) brute force will explore this space considering all solutions equally
Linear searching can said to be a special case of Brute- force method.
Brute-force method is a broader category according to which every option available is checked for the best possible answer, while linear search also compares the key element with every element in the series but it would then be just stopped as soon as the element is found and would not check further if the element is present in the series again later.
Pseudocode
int key;
int array[];
for (int i=0; i<array.length(); i++) {
if(array[i] == key) {
return i; }
}
return -1;
Java Code for Linear Search
public class LinearSearch {
public static int linearSearch(int[] arr, int key) {
int size = arr.length;
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
return i;
}
}
//This is the default value if the key is not found in the array.
return -1;
}
public static void main(String a[]) {
int[] arr1 = {23, 45, 21, 55, 234, 1, 34, 90};
int searchKey = 34;
System.out.println("Key " + searchKey + " found at index: " + linearSearch(arr1, searchKey));
int[] arr2 = {123, 445, 421, 595, 2134, 41, 304, 190};
searchKey = 421;
System.out.println("Key " + searchKey + " found at index: " + linearSearch(arr2, searchKey));
}
}
Analysis of Linear Search
For an array with n entries, the algorithm takes n steps in the worst case. Hence, it follows O(n). In the video below, you will see how linear search fares if you’re looking to search for a card of your choice from an entire dec
Best case =O(1)
worse case =O(n)
Divide and Conquer
If the problem is divided into subproblems, the number of steps required to solve it reduces significantly.
Binary Search
For binary search, you need a sorted array. You can not apply binary search on an array thats not sorted. You start at the middle index and compare the element you’re searching for with the element at the middle index. If the element at this index does not match the element you’re searching for, you check if it is greater or lesser than the element at the index. If it is greater than the element at the middle index, you discard everything to the left and move to the right. You then find the middle of this array that’s to the right, compare the required element with its middle, and keep doing this till you find the required element.
In binary search algorithm, after every search operation, the search gets reduced by 1/2. For example, if we are given a sequence as {0,1,3,4,5,7,8,9 },and we are searching for 1, then according to binary search we will first find the middle element which in this case will be at, 0+7/2 =3.5~3, third position, i.e “4”. Now we will compare our key “1” to “4” , as they are not equal now we will see if our key is greater than 4 or less than 4. We conclude that it is less than 4, now the search zone is narrowed to “0” to 3-1 = “2” (3 was the position of our current middlemost element)
Next we have to search “1” with elements at position {0,1,2}. Before this step, the total number of elements in the sequence we had was “7”, searching sequentially we should have compared it to all 7 elements, but with binary searching we are only comparing it with maximum 3 elements that is almost half of the total elements. Hence after every step the search zone is narrowed to ½.
public class BinarySearch {
public int binarySearch(int[] inputArr, int key) {
int start = 0;
int end = inputArr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (key == inputArr[mid]) {
return mid;
}
if (key < inputArr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
BinarySearch mbs = new BinarySearch();
int[] arr = {2, 4, 6, 8, 10, 12, 14, 16};
System.out.println("Key 14's position: " + mbs.binarySearch(arr, 14));
int[] arr1 = {6, 34, 78, 123, 432, 900};
System.out.println("Key 432's position: " + mbs.binarySearch(arr1, 432));
}
}
Time Complexity of Binary Search
Basically, in the first step you check if the element you are searching for is equal to the middle element or not. So this is the equality check which is the first comparison. In the next step you check if the element is greater than or less than the middle element. Here we are not checking their equality but we are comparing them to check which of them is greater than the other. So, this is the secod comparison.
T(n) = 2 +T(n/2) , where T(n) denotes the total number of comparisons.
T(n/2) = 2 +T(n/4)
Divide and conquer led to a new search technique called binary search. This follows a O(log n) complexity, which is much more efficient than linear search.