Learn Interpolation search in 8 minutes ❓

แชร์
ฝัง

ความคิดเห็น • 47

  • @BroCodez
    @BroCodez  2 ปีที่แล้ว +18

    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

    • @joyceasante8292
      @joyceasante8292 ปีที่แล้ว

      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

  • @marcovic9916
    @marcovic9916 2 ปีที่แล้ว +11

    This search algorithm is crazy, never heard of that! I'll definitely remind this and maybe should tell my prof about. Nice video bro :)

  • @nutcoatz6230
    @nutcoatz6230 2 ปีที่แล้ว +2

    this guy is the most underrated channel ever, like holy shit this guy is good at teaching, keep it up man don't stop!

  • @mikedabramo2001
    @mikedabramo2001 3 หลายเดือนก่อน

    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!

  • @vovagusse
    @vovagusse 2 ปีที่แล้ว +6

    Binary search, *BUT BETTER?!*
    Thanks! Saving it to my playlist with no hesitations!

    • @BroCodez
      @BroCodez  2 ปีที่แล้ว +9

      better but IF the data is about evenly distributed

  • @Dertgyhud
    @Dertgyhud 2 ปีที่แล้ว +1

    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.

  • @gabrielcapone4332
    @gabrielcapone4332 2 ปีที่แล้ว +1

    These algorithm videos are great bro :)

  • @Ashish-yq9lg
    @Ashish-yq9lg 2 ปีที่แล้ว +8

    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 😀

  • @cranebird1467
    @cranebird1467 2 ปีที่แล้ว

    Thanks a lot ! Great job, advanced biSearch.

  • @keithwalter7136
    @keithwalter7136 2 ปีที่แล้ว

    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!

  • @user-cs5oj6vw7z
    @user-cs5oj6vw7z 8 หลายเดือนก่อน +1

    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.👌👌👌👌👌👌👌👌

  • @oogshow2809
    @oogshow2809 2 ปีที่แล้ว

    its really nice explanation with quite voice , thanks bro

  • @najmulislam9658
    @najmulislam9658 2 ปีที่แล้ว

    Thanks Bro, For This Video. You ara A Good Parson. I Like Your Video all time. Your Fan From "Bangladesh".

  • @neil_armweak
    @neil_armweak 2 ปีที่แล้ว

    Well done

  • @Anonymationsthecoolanimator
    @Anonymationsthecoolanimator 2 ปีที่แล้ว

    Oh, this is something new and interesting. I thought only linear search and binary search existed😅

  • @juanivillanueva7873
    @juanivillanueva7873 ปีที่แล้ว

    I'm in the third year of my CS career and I have never heard of this type of search!

  • @FukSN
    @FukSN 2 ปีที่แล้ว

    Not 1st to see 😁 but appreciated never the less.
    Thanks Bro 👍

  • @omggodbs
    @omggodbs 2 ปีที่แล้ว

    yo i went from zero to hero cuz of ur content :)

  • @victorrezende6002
    @victorrezende6002 8 หลายเดือนก่อน

    Nice class

  • @BananaMan6763
    @BananaMan6763 หลายเดือนก่อน

    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#?

  • @TheEvertonDias
    @TheEvertonDias 10 หลายเดือนก่อน

    Thanks, Bro!

  • @MrLoser-ks2xn
    @MrLoser-ks2xn ปีที่แล้ว

    Thanks!

  • @jaymar921
    @jaymar921 2 ปีที่แล้ว

    Hello bro, cool vid 😎

  • @thealmightytitan4006
    @thealmightytitan4006 2 ปีที่แล้ว

    thanks

  • @Anonymationsthecoolanimator
    @Anonymationsthecoolanimator 2 ปีที่แล้ว +1

    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?

    • @coder4937
      @coder4937 2 ปีที่แล้ว

      Try it yourself 🙃

  • @ricardochica4339
    @ricardochica4339 2 ปีที่แล้ว

    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

  • @oogshow2809
    @oogshow2809 2 ปีที่แล้ว

    bro one request we need class of 3d game developement in java

  • @yaboijones
    @yaboijones ปีที่แล้ว +1

    can someone explain to me how probing works?
    how does the formula guess where the value is?

  • @princeangelo7051
    @princeangelo7051 2 ปีที่แล้ว

    ❤️❤️❤️ first to see ❤️❤️

  • @marcel_wendler
    @marcel_wendler 2 ปีที่แล้ว

    As what are you working?

  • @ucPham-yq2qy
    @ucPham-yq2qy 3 หลายเดือนก่อน

    but when arr[low] == arr[high] and low != high, how this search algorithm work?

  • @pogchamp2973
    @pogchamp2973 2 ปีที่แล้ว +1

    Poggersss

  • @typingcat
    @typingcat 6 หลายเดือนก่อน

    What exactly does "uniformly distributed" mean here? The example series seem only increasing. What's uniform? You mean, increasing by a fixed rate?

  • @cedric6941
    @cedric6941 2 ปีที่แล้ว

    gg

  • @n23hsa1
    @n23hsa1 8 หลายเดือนก่อน

    Does anybody know where I can find a proof of the average case?

    • @maccollo
      @maccollo 3 หลายเดือนก่อน

      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

  • @shivamthakur1226
    @shivamthakur1226 ปีที่แล้ว

    Random Comment

  • @Nagar2024
    @Nagar2024 ปีที่แล้ว

    I think this is giving wrong ans for array
    {10,20,30,40,50}

    • @duongpham6112
      @duongpham6112 11 หลายเดือนก่อน

      It is working perfectly, check algorithm again.

  • @fyrukmcoo100
    @fyrukmcoo100 2 ปีที่แล้ว

    :((

  • @Trapped8283
    @Trapped8283 8 หลายเดือนก่อน

    my brain is defective I cant understand