//interpolation search = improvement over binary search best used for "uniformly" distributed data // "guesses" where a value might be based on calculated probe results // if probe is incorrect, search area is narrowed, and a new probe is calculated
Practicing... import java.util.*; public class Main { public static void main(String[] args) { int[]array = {1,2,4,8,16,32,64,128,256,512,1024}; int index = interpolationSearch(array,1024); if(index != -1){ System.out.println("Element found at index: "+ index); } else{ System.out.println("Element not found"); } } private static int interpolationSearch(int[]array, int value){ int high = array.length - 1; int low = 0; while(value >= array[low] && value
I'm transitioning out of teaching into programming/IT, and the biggest obstacle I've faced so far is learning from someone who can explain challenging material in a way that a novice can understand. You obviously know the material, but what sets you apart is your ability to teach it well. Outstanding job!
Can you make videos with some complex examples where we can code side by side with your videos for like arraylists, searching, sorting etc. That would be really helpful in understanding the use of them in different situations. Anyway Thanks for the free courses 😀
Assolomu Alaykum ! Bro your videos so helpfull and better to undestand. Can you give more definations and explanations to probe function ! Thank you ! For free sharing your videos.👌👌👌👌👌👌👌👌
I love the explanation and I learned a lot. I also would like to learn for 2 or more array factors which we can guess the interpolated value using these given multiple set of arrays. Would love to watch that maybe in the series of this video? Either way, thanks so much bro!
In these videos where these concepts can be applied to programming you show examples of using them with programming in Java, and it has helped me understand a bit, it’s just that I’m not learning Java, I’m learning c#. Would it be ok for me to look at your examples to understand how the concepts work when applied to programming and then try to learn how to use them with c#?
these are general stuff and not really restricted to a language , you could apply the same concept and logic throughout other languages and it would be completely fine. actually most other stuff are the same , its rare to find a general concept that doesnt apply to all languages ( Dsa is an example , multithreading basics , data collections , networking , api design , sql basics)
One question, this will work only if array is sorted and the data is either in Geometric progression or arithmetic progression. Will it also work in arithmetic-geometric progression and harmonic progression?
omg, this algorithm is crazy! Although, I'm not sure if I'm doing this one correctly or what's going on: I'm using an array populated by random elements bound in 200. It has 100000 elements, and they have been sorted. I do this search function as explained but only throws 1 probe, or 2 at the most each time, how is that possible that it guesses almost every time correctly? int[] array3 = new int[100000]; Random random = new Random(); for (int i = 0; i < 100000; i++) array3[i] = random.nextInt(200); Arrays.sort(array3); int interpSearch = 123; int index3 = interpolationSearch(array3, interpSearch); System.out.println(); if(index3 != -1) { System.out.println("Element found at index: " + index3); System.out.println("Array index: " + index3 + "\tValue:" + array3[index3]); } else System.out.println("Element not found"); } And here's the method: private static int interpolationSearch(int[] array, int value){ long start; long end; long elapsed; start = System.nanoTime(); int high = array.length - 1; int low = 0; while(value >= array[low] && value
It's basically the secant method, so you should probably look for proofs regarding it's convergence rate. For sufficiently large datasets you can treat it the same as finding the root of a real valued functions in the interval [0,1], and find how many steps until the error is < 1/n
![Gunna - HIM ALL ALONG [Official Visualizer]](http://i.ytimg.com/vi/HiCxoDeo0hc/mqdefault.jpg)
public class Main{
public static void main(String args[]){
//interpolation search = improvement over binary search best used for "uniformly" distributed data
// "guesses" where a value might be based on calculated probe results
// if probe is incorrect, search area is narrowed, and a new probe is calculated
// average case: O(log(log(n)))
// worst case: O(n) [values increase exponentially]
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int index = interpolationSearch(array, 8);
if(index != -1) {
System.out.println("Element found at index: "+ index);
}
else {
System.out.println("Element not found");
}
}
private static int interpolationSearch(int[] array, int value) {
int high = array.length - 1;
int low = 0;
while(value >= array[low] && value
Practicing...
import java.util.*;
public class Main
{
public static void main(String[] args) {
int[]array = {1,2,4,8,16,32,64,128,256,512,1024};
int index = interpolationSearch(array,1024);
if(index != -1){
System.out.println("Element found at index: "+ index);
}
else{
System.out.println("Element not found");
}
}
private static int interpolationSearch(int[]array, int value){
int high = array.length - 1;
int low = 0;
while(value >= array[low] && value
This search algorithm is crazy, never heard of that! I'll definitely remind this and maybe should tell my prof about. Nice video bro :)
this guy is the most underrated channel ever, like holy shit this guy is good at teaching, keep it up man don't stop!
I'm transitioning out of teaching into programming/IT, and the biggest obstacle I've faced so far is learning from someone who can explain challenging material in a way that a novice can understand. You obviously know the material, but what sets you apart is your ability to teach it well. Outstanding job!
Can you make videos with some complex examples where we can code side by side with your videos for like arraylists, searching, sorting etc. That would be really helpful in understanding the use of them in different situations. Anyway Thanks for the free courses 😀
Binary search, *BUT BETTER?!*
Thanks! Saving it to my playlist with no hesitations!
better but IF the data is about evenly distributed
Can’t believe you are at 200K subscribers. I was one of the first subscribers when you started around November 2019. I went by Dan Savage then.
I'm in the third year of my CS career and I have never heard of this type of search!
Assolomu Alaykum !
Bro your videos so helpfull and better to undestand.
Can you give more definations and explanations to probe function !
Thank you ! For free sharing your videos.👌👌👌👌👌👌👌👌
I love the explanation and I learned a lot. I also would like to learn for 2 or more array factors which we can guess the interpolated value using these given multiple set of arrays. Would love to watch that maybe in the series of this video? Either way, thanks so much bro!
These algorithm videos are great bro :)
In these videos where these concepts can be applied to programming you show examples of using them with programming in Java, and it has helped me understand a bit, it’s just that I’m not learning Java, I’m learning c#. Would it be ok for me to look at your examples to understand how the concepts work when applied to programming and then try to learn how to use them with c#?
these are general stuff and not really restricted to a language , you could apply the same concept and logic throughout other languages and it would be completely fine.
actually most other stuff are the same , its rare to find a general concept that doesnt apply to all languages ( Dsa is an example , multithreading basics , data collections , networking , api design , sql basics)
Thanks a lot ! Great job, advanced biSearch.
Thanks Bro, For This Video. You ara A Good Parson. I Like Your Video all time. Your Fan From "Bangladesh".
its really nice explanation with quite voice , thanks bro
One question, this will work only if array is sorted and the data is either in Geometric progression or arithmetic progression. Will it also work in arithmetic-geometric progression and harmonic progression?
Try it yourself 🙃
omg, this algorithm is crazy! Although, I'm not sure if I'm doing this one correctly or what's going on:
I'm using an array populated by random elements bound in 200.
It has 100000 elements, and they have been sorted.
I do this search function as explained but only throws 1 probe, or 2 at the most each time, how is that possible that it guesses almost every time correctly?
int[] array3 = new int[100000];
Random random = new Random();
for (int i = 0; i < 100000; i++) array3[i] = random.nextInt(200);
Arrays.sort(array3);
int interpSearch = 123;
int index3 = interpolationSearch(array3, interpSearch);
System.out.println();
if(index3 != -1) {
System.out.println("Element found at index: " + index3);
System.out.println("Array index: " + index3 + "\tValue:" + array3[index3]);
}
else System.out.println("Element not found");
}
And here's the method:
private static int interpolationSearch(int[] array, int value){
long start;
long end;
long elapsed;
start = System.nanoTime();
int high = array.length - 1;
int low = 0;
while(value >= array[low] && value
Oh, this is something new and interesting. I thought only linear search and binary search existed😅
yo i went from zero to hero cuz of ur content :)
Thanks, Bro!
can someone explain to me how probing works?
how does the formula guess where the value is?
Nice class
What exactly does "uniformly distributed" mean here? The example series seem only increasing. What's uniform? You mean, increasing by a fixed rate?
Correct
Thanks!
bro one request we need class of 3d game developement in java
Well done
Hello bro, cool vid 😎
Thanks
but when arr[low] == arr[high] and low != high, how this search algorithm work?
As what are you working?
but ho do we get that formula of probe?
sweeeet
❤️❤️❤️ first to see ❤️❤️
no I was
Does anybody know where I can find a proof of the average case?
It's basically the secant method, so you should probably look for proofs regarding it's convergence rate.
For sufficiently large datasets you can treat it the same as finding the root of a real valued functions in the interval [0,1], and find how many steps until the error is < 1/n
Poggersss
I think this is giving wrong ans for array
{10,20,30,40,50}
It is working perfectly, check algorithm again.
gg
Random Comment
my brain is defective I cant understand
:((
thanks