Linear Search Algorithm
Searching :
It is a process of finding given value position in a list of values.
- Linear/Sequential Search:
- It is basic of simple search algorithm
- In sequential search, we compare the target value with all the other elements given in the list.
E.g.:- arr[14, 234, 34, 53, 54] (unsorted array)
target = 53
In above example, the target value is compared with all the elements in array in
sequential/linear way.
Time complexity
Best case : O(1) → constant.
-
How many checks will the loop make in best case i.e the element will be found at
0th index.
i.e, only one comparision will be made for best case.
Worst case : O(n)
- Worst case, when it will go though every element and then it says element not found.
Size of array
No. of comparisons
time (ms)
100
100
100 ms
200
200
200 ms
n
n
public class Binary {
public static void main(String[] args) {
int[] nums = { 23, 45, 1, 2, 8, 19, -3, -11, 28 };
int target = 19;
System.out.println(linearSearch(nums, target));
}
// serach in the array: return the index if item found
// otherwise if item not found return -1
static int linearSearch(int[] arr, int target) {
if (arr.length == 0) {
return -1;
}
// run a for loop
for (int i = 0; i < arr.length; i++) {
// check of element at every index if it is = target
if (arr[i] == target) {
return i;
}
}
// this line will execute if none of the reutn statements
// above have executed
//hence the target not found
return -1;
}
}
This also works for searching inside strings
public class SearchInStrings {
public static void main(String[] args) {
String name = "heyhey";
char target = 'e';
System.out.println(search(name,target));
}
static boolean search(String name, char target) {
if(name.length() == 0){
return false;
}
for (int i = 0; i < name.length(); i++) {
if(target == name.charAt(i)){
return true;
}
}
return false;
}
}
Now using for each
public class SearchInStrings {
public static void main(String[] args) {
String name = "heyhey";
char target = 'e';
System.out.println(search2(name,target));
}
static boolean search(String name, char target) {
if(name.length() == 0){
return false;
}
for (char ch : name.toCharArray()) {
if(ch == target){
return true;
}
}
return false;
}
}
Search in range of index
Every thing is same but only we have to search between some given starting and last index.
E.g.:-
public class SearchRange {
public static void main(String[] args) {
String name = "heyhey";
char target = 'e';
System.out.println(search(name, target, 2, 4));
}
static boolean search(String name, char target, int start, int end) {
if (name.length() == 0) {
return false;
}
for (int i = start; i <= end; i++) {
if (target == name.charAt(i)) {
return true;
}
}
return false;
}
}
Search in 2D array
public class Search2d {
public static void main(String[] args) {
int[][] arr = {
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 }
};
int target = 99;
System.out.println(search(arr, target));
}
static int search(int[][] arr, int target) {
for (int[] row : arr ) {
for (int i = 0; i < row.length; i++) {
if(target==row[i]){
return 1;
}
}
}
return -1;
}
}
Given an array nums of integers, return how many of them contain an even number of digits. leetcode
public class EvenNumLeet {
public static void main(String[] args) {
int[] arr = { 2, 34, 55, 66666, 666 };
System.out.println(findNumbers(arr));
}
static int findNumbers(int[] arr) {
// If number is negative then
// we are making it positive
if(num<0){
num*=-1;
}
// if num is 0 the while loop will not run
// so just return 1
if(num==0){
return 1;
}
int times = 0;
int count = 0;
for (int num : arr) {
int temp = num;
while (temp > 0) {
times++;
temp /= 10;
}
if (times % 2 == 0) {
count++;
}
times = 0;
}
return count;
}
// most optimized way to find number of digits
// using this formula
static int digits2(int num) {
if (num < 0) {
num = num * -1;
}
return (int)(Math.log10(num)) + 1;
}
}
Max wealth leetcode
class Solution {
public int maximumWealth(int[][] accounts) {
int maxWealth = 0;
for(int[] cus : accounts){
int sum = 0;
for(int i = 0; i < cus.length ; i++){
sum = sum + cus[i];
}
if(sum>maxWealth){
maxWealth = sum;
}
}
return maxWealth;
}
}