//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 😀
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!
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.👌👌👌👌👌👌👌👌
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#?
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
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!
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.
These algorithm videos are great bro :)
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 😀
Thanks a lot ! Great job, advanced biSearch.
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!
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.👌👌👌👌👌👌👌👌
its really nice explanation with quite voice , thanks bro
Thanks Bro, For This Video. You ara A Good Parson. I Like Your Video all time. Your Fan From "Bangladesh".
Well done
Oh, this is something new and interesting. I thought only linear search and binary search existed😅
I'm in the third year of my CS career and I have never heard of this type of search!
Not 1st to see 😁 but appreciated never the less.
Thanks Bro 👍
yo i went from zero to hero cuz of ur content :)
Nice class
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#?
Thanks, Bro!
Thanks!
Hello bro, cool vid 😎
thanks
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
bro one request we need class of 3d game developement in java
can someone explain to me how probing works?
how does the formula guess where the value is?
❤️❤️❤️ first to see ❤️❤️
no I was
As what are you working?
but when arr[low] == arr[high] and low != high, how this search algorithm work?
Poggersss
What exactly does "uniformly distributed" mean here? The example series seem only increasing. What's uniform? You mean, increasing by a fixed rate?
Correct
gg
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
Random Comment
I think this is giving wrong ans for array
{10,20,30,40,50}
It is working perfectly, check algorithm again.
:((
my brain is defective I cant understand