|
Be the first user to complete this post
|
Add to List |
382. Linear Search vs Binary Search
Earlier we have seen linear search and binary search and how these work individually, In this article we will compare these two search algorithms. If you are new to these, please read the prerequisites below-
Prerequisites:
| SNo | Linear Search | Binary Search |
| 1 | Works with a sorted or unsorted array. | Works with sorted arrays only |
| 2 | Simple scan – iterates and compares one item at a time, either left to right or vice versa. | Removes half of the items after each comparison until the element is not found |
| 3 | For an array, iterate from the beginning to the end, and test each item in the array | After 1st iteration, N/2 items remain (N/21) After 2nd iteration, N/4 items remain (N/22) After 3rd iteration, N/8 items remain (N/23) |
| 4 |
static void search(int [] input, int x){
for (int i = 0; i <input.length ; i++) {
if(x==input[i]) {
System.out.println("Element " + x + " is found at index: " + i);
return;
}
}
//if here means x is not found
System.out.println("Element " + x + " is not found in array");
}
|
If(mid_element==key) return true; else if (mid>key) do a recursive search on the right half of the array. else do a recursive search on the left half of the array. |
| 5 | Time Complexity: O(N) | Time Complexity: Log2N |
Please see the code below and run on IDE for better understanding.
Output:
Linear Search.....Element 14 is found at index: 5 Binary Search.....Element 14 is found in array at index: 5 Linear Search.....Element 21 is not found in the array Binary Search.....Element 21 is not found in the array