Algorithms :Linear Search-part 1
Linear Search part 1:
Let find 4 index number from arr variable using Linear Searching. (This is normal linear search)
function linearSearch(arr,key){
for(let i=0; i < arr.length; i++){
if(arr[i]==key){
return i;
}
}
}
let arr = [5,74,2,32,5,21,4];
let key =4;
let position = linearSearch(arr,key);
console.log(position);
output: 6
Let find 23 index number from arr variable using Linear Searching. (This is normal linear search)
function linearSearch(arr,key){
for(let i=0; i < arr.length; i++){
if(arr[i]==key){
return i;
}
}
}
let arr = [5,74,2,32,5,21,4];
let key = 32;
let position = linearSearch(arr,key);
console.log(position);
output: 3
Let find all 5 index number from arr variable using Linear Searching. (This is Global linear search)
function globalLinearSearch(arr,key){
let result = [];
for(let i=0; i < arr.length; i++){
if(arr[i]==key){
result.push(i);
}
}
return result;
}
let arr = [5,74,2,32,5,21,4,5];
let key = 5;
let allPosition = globalLinearSearch(arr,key);
console.log(allPosition);
output: [ 0, 4, 7 ]
Binary Search
Any search space where we can divide the search space in two halves, where two halves can be distinguished based won same properly and then we discard of those halves based on that property, is called binary search.
One of the example of Binary Search is Monotonic Curve.
function binarySearch(arr, key){
let start = 0;
let end = arr.length -1;
while (start <= end){
let mid = Math.floor((start + end), 2);
if(arr[mid] ==key){ // found the key element
return mid;
}
// key element is smaller than mid element ->
else if (key < arr[mid]) {
end = mid -1;
}
// key element is greater is than mid element -> right
else {
start = mid + 1;
}
}
return NaN;
}
let arr = [2,10,14,17,22,25,29,34,39,41];
let key = 10;
let position = binarySearch(arr,key);
console.log(position);
output: 1
function binarySearch(arr, key){
let start = 0;
let end = arr.length -1;
while (start <= end){
let mid = Math.floor((start + end), 2);
if(arr[mid] ==key){ // found the key element
return mid;
}
// key element is smaller than mid element ->
else if (key < arr[mid]) {
end = mid -1;
}
// key element is greater is than mid element -> right
else {
start = mid + 1;
}
}
return NaN;
}
let arr = [2,10,14,17,22,25,29,34,39,41];
let key = 11;
let position = binarySearch(arr,key);
console.log(position);
output: NaN
Questions:
Solution:
function searchUnique(arr,start,end){
// base case
if(start > end){
return;
}
if(start == end){ // unique element found
return start;
}
let mid = start + Math.floor((end -start)/2);
// check if mid is even
if(mid%2 == 0){
if(arr[mid] == arr[mid+1]){
//search on right
return searchUnique(arr,mid+2, end);
}
else{
// search on left
return searchUnique(arr,start,mid);
}
}else{ // mid is odd
if(arr[mid] == arr[mid-1]){
// search on right
return searchUnique(arr, mid+1, end);
}
else{
// search on left
return searchUnique(arr,start,mid);
}
}
}
let arr = [1,1,3,3,5,5,7,7,9,11,11,15,15];
let start = 0;
let end = arr.length-1;
let position = searchUnique(arr,start,end)
console.log("element:",arr[position]," position:",position);
output:
element: 9 position: 8
Algorithms : Binary Search-part-2
Ternary Search
function ternarySearch(arr,key,start, end){
if(start > end){ // base case
return NaN;
}
// self work
// 9/3 =3 => mid1
// 2*9/3 = 6 => mid2
let mid1 = Math.floor(start +(end-start)/3);
let mid2 = Math.floor(end- (end - start)/3);
console.log(start,end,mid1,mid2);
if(arr[mid1] == key){
return mid1;
}
if(arr[mid2] == key){
return mid2;
}
if(key < arr[mid1]){ // first part
return ternarySearch(arr, key,start,mid1-1)
}
else if(key > arr[mid2]){ // third part
return ternarySearch(arr, key,mid2+1,end)
}
else{ // second part
return ternarySearch(arr,key,mid1+1,mid2-1);
}
}
let arr = [1,2,4,6,7,10,20,50,100,200]
let start = 0;
let end = arr.length -1;
let key = 50;
let position = ternarySearch(arr,key,start,end);
console.log(position);
output:
0 9 3 6
7 9 7 8
7
Linked Lists and its variants
A linked list is a linear data structure used to store data collection.
Array is a basic Data structure
Array is a Linear Data structure
Array is not Dynamic.
Three types of linked list
Single Linked List
Doubly Linked List
Circular Linked List
A linked list is a Dynamic ----> It can grow or shrink in size during your program execution.
This is How to create One node
Node is part Linked List.
Node and Linked List are different.
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
let x = new Node([1,2,3,4,"Abc",[11,12]]);
console.log(x.data);
console.log(x.next);
output:
[ 1, 2, 3, 4, 'Abc', [ 11, 12 ] ]
null
// Node class
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
let x = new Node(10);
console.log(x.data);
console.log(x.next);
output:
10
null
Single Linked List
// Node class
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
// Linked list Class
class SinglyLinkedList {
constructor(){
this.head = null;
this.length = 0;
}
insertAtStart(data){
let newNode = new Node(data); // create a new node with data.
newNode.next = this.head; // attach new node at the start or current head.
this.head = newNode; // Update the head pointer to new node.
this.length++;
}
}
let myLinkedList = new SinglyLinkedList();
console.log(myLinkedList.head);
console.log(myLinkedList.length);
myLinkedList.insertAtStart(10);
console.log(myLinkedList.head);
console.log(myLinkedList.length);
myLinkedList.insertAtStart(20);
console.log(myLinkedList.head);
console.log(myLinkedList.length);
myLinkedList.insertAtStart(30);
console.log(myLinkedList.head);
console.log(myLinkedList.length);
output:
null
0
Node { data: 10, next: null }
1
Node { data: 20, next: Node { data: 10, next: null } }
2
Node {
data: 30,
next: Node { data: 20, next: Node { data: 10, next: null } }
}
3
insert
// Node class
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
// Linked list Class
class SinglyLinkedList {
constructor(){
this.head = null;
this.length = 0;
}
insertAtStart(data){
let newNode = new Node(data); // create a new node with data.
newNode.next = this.head; // attach new node at the start or current head.
this.head = newNode; // Update the head pointer to new node.
this.length++;
}
printLinkedList(){
let currNode = this.head;
while(currNode != null){
console.log(currNode.data);
currNode = currNode.next;
}
}
}
let myLinkedList = new SinglyLinkedList();
console.log(myLinkedList.head);
console.log(myLinkedList.length);
myLinkedList.insertAtStart(10);
console.log(myLinkedList.head);
console.log(myLinkedList.length);
myLinkedList.insertAtStart(20);
console.log(myLinkedList.head);
console.log(myLinkedList.length);
myLinkedList.insertAtStart(30);
console.log(myLinkedList.head);
console.log(myLinkedList.length);
console.log("---------------------------------------");
myLinkedList.printLinkedList();
output:
null
0
Node { data: 10, next: null }
1
Node { data: 20, next: Node { data: 10, next: null } }
2
Node {
data: 30,
next: Node { data: 20, next: Node { data: 10, next: null } }
}
3
---------------------------------------
30
20
10
.png)