How to explain binary search to my sister? This is really difficult, fan!

Every day in the morning It's seven thirty , Push dry goods on time

Ah fan was almost stumped by her sister , Let me talk about the details slowly

What is binary search

During lunch a few days ago , The girl in the team suddenly asked me , What is binary search .

Make ah fan a little confused , What do you mean , This is testing me ？ If I say the definition of binary search, wouldn't it make me too bookish , It's not fun ？ This is not in line with ah fan's character , Suddenly, my brain became excited and I had an idea .

Afan ： Before we talk about binary search , Let's play a game . The price of this short sleeve I wear is 100 within , Guess the actual price ？ Just say the numbers , If I say too much, I'll say you say too much , If I say less, I will answer truthfully , Until you get the right answer .

sister ：100 within ？ yes 50 Do you ？

Afan ： You said less , Guess again .

sister ：75 ？

Afan ： Less said , Guess again .

sister ：88 ？

Afan ： You guessed right this time ！ Take a closer look at the process of your guess , The first guess was 50 , Why not other numbers ？

sister ： Because you said the price was 100 within , if 50 Words , You told me too much , That's less than 50 I don't have to care 了 , If it is less , That's bigger than that 50 I don't have to guess the number of , In this way, you can guess the correct answer relatively faster .

Afan ： You think like this , It reflects the binary search . The process of binary search is , Start with the middle element of the array , If the middle element is exactly the element to find , Then the search process is over ; If a particular element is greater than or less than the middle element , Find in the half of the array that is larger or smaller than the middle element , And it's the same as the beginning, starting from the middle element ; Until you find the number you want . Yes, of course , In the process , You may not find the number you are looking for .

sister ： Oh , So this is binary search , It's quite simple , Ha ha ha ha

Afan ： It's not simple , If you don't believe it , Try writing code , See if it can be realized .

As soon as ah fan finished speaking, she saw her sister trying to knock the code

For a while , The sister wrote the code :

Log in and copy

       

        public static int binarySearch(int[] arr, int n, int value){
        
    int low = 0;
        
    int high = n-1;
        

        
    while (low 
        <
        = 
        high){
        

        /
        / 
         Define intermediate values  
        mid 
        

        int 
        mid = 
        low 
        + 
        (( 
        high 
        - 
        low) 
        >> 1);
        
  //  If  arr[mid] == value , Then the middle number at this time is the desired , Just go back 
        
  //  If  arr[mid] != value , Change the value range 
        
        if ( arr[mid] == value){
        
            return mid;
        
        }else if( arr[mid] 
        < 
        value){
        

        low = 
        mid 
        + 
        1;
        

        }else{
        

        high = 
        mid 
        - 
        1;
        

        }
        

        }
        

        /
        / 
        while 
         The required number is still not found at the end of the cycle , That is, there is no 
        

        return 
        -1;
        

        }
        

        

        public 
        static 
        void 
        main(String[] 
        args){
        

        int[] 
        arr =
        {1,37,8,27,13,66,25,30,47,95};
        

        

        /
        / 
         call  
        BinarySearch 
        

        int 
        binarySearch = 
        binarySearch(arr,arr.length,27);
        

        

        System.out.println(binarySearch);
        

        }
       
       

        
1.
        
2.
        
3.
        
4.
        
5.
        
6.
        
7.
        
8.
        
9.
        
10.
        
11.
        
12.
        
13.
        
14.
        
15.
        
16.
        
17.
        
18.
        
19.
        
20.
        
21.
        
22.
        
23.
        
24.
        
25.
        
26.
        
27.
        
28.
        
29.
       

sister ： Little brother fan , Why is the program I wrote wrong , There is 27 , Why is the value given to me by the running result -1 Well

A fan has a look , It's really , What's the matter? , Mingming binarySearch There is nothing wrong with that part of the code , Why can't it run , A fan looked sweating

Suddenly ah fan saw the array defined by sister , Suddenly understand .

Afan ： Do you know the premise of using binary search ？

sister ： Clitoris ？ Why are there preconditions ？ You didn't tell me just now

Afan ： Let's go back to the game we just played together , At the beginning, you guessed 50 , Then greater than 50 Words , Less than 50 Let's not consider whether it's right , So do we default that the whole array is ordered , So we can not care less than 50 The number of the , Am I right? ？

sister ： You say so , That's right . So the array I defined is not ordered , When binary search this array , Will check 13 , The number I'm looking for is 27 , Greater than 13 , So the program looks back , But there is no more 27 了 , So it will return to me -1

Afan ： Yes ！ You are too clever, aren't you . Turn the numbers in the array into order and you can get the result you want .

sister ： wow , Little brother fan , Really , The program returned me the correct result . You are really great

Ah fan blushed again after being praised ...

About binary search , Ladies and gentlemen get Did you? ~

< END >