[interview: Basics 01: integer binary search]

【 interview ： The basic chapter 01： Integer binary search 】

00. Preface

Hello everyone, I'm a sophomore , Currently, I am practicing , In the big guy @ Tiejia Xiaobao With the help of csdn Update blog on , Your advice are most welcome .
Please point out any questions about what I wrote , Thank you .

01. brief introduction

Binary search is a kind of search algorithm , In the case of sequence ${\log }_2^N$ Good time complexity

02. Algorithm steps

stay {1,3,5,6,7,9,13,25,34,61,88} in total 11 Of the elements find 25 Steps for , Specify subscript from 0 Start

1. First we choose the subscript 0,10 As the left and right boundaries l,r In the middle mid=(l+r)/2, Be careful ： there l+r All are integers except 2 If the result of is decimal, round down
2. Now our mid=5, Element 9 It's not equal to 25, Then we make l=mid+1, Be careful ： Here is mid+1 instead of mid Because we have determined mid The element corresponding to this subscript is not equal to 25 So between us from mid+1 Just start looking
3. Now our l=6 r=10,mid=(l+r)/2=8 Element 34, here 34 Greater than 25, We make r=mid-1
4. Now our l=6 r=7,mid=(l+r)/2=6 Element 13 Make l=mid+1
5. Now our l=7 r=7,mid=(l+r)/2=7 Element 25 Found the element 25 At this time, the corresponding subscript is returned 7

It can be seen that we found the result after a total of four searches

03. Algorithm implementation

public static void main(String[] args) {
    
        int[] a = {
    1,3,5,6,7,9,13,25,34,61,88};//  Sorted array 
        int res= 25;// Number to find 
        int result = Search(a,res);
        System.out.println(result);
    }

    private static int Search(int[] a,int res) {
    
        int l=0,r=a.length-1;
        while (l<=r){
    
            System.out.println("l:"+l+" r:"+r);
            int mid = (l+r)/2;
            if (a[mid]<res){
    
                l=mid+1;
            }else if (a[mid]>res){
    
                r=mid-1;
            }else{
    
                return mid;
            }
        }
        return -1;
    }

result

l:0 r:10
l:6 r:10
l:6 r:7
l:7 r:7
7

It can be seen that it is the same as our reasoning Four times The final result is subscripted 7

04. Optimize mid Spillover problem

Introduction to the problem ：

When we mid=(l+r)/2 when l+r If the value is too large, it will overflow

Example

public static void Overflow(){
    //  Integer overflow problem 
        int l=0,r=Integer.MAX_VALUE-1;
        int mid = (l+r)/2;
        System.out.println(mid);
        l=mid+1;
        mid = (l+r)/2;
        System.out.println(mid);// mid Too large overflow 
    }

result

-536870913, And you can see that at this point mid It's overflowing

resolvent 1

public static void Overflow1(){
    //  Integer overflow problem 
    int l=0,r=Integer.MAX_VALUE-1;
    int mid = (l+r)/2;
    l=mid+1;
    mid = (l+r)/2;
    System.out.println(mid);// mid Too large overflow 
    // At this time, we change the form 
    mid = l+(r-l)/2;
    System.out.println(mid);//  It can be seen that there is no overflow at this time 
}

result

-536870913 // The result of overflow
1610612735 // The result of changing the form

It can be seen that the overflow is prevented at this time

resolvent 2

private static void Overflow2() {
    
    int l=0,r=Integer.MAX_VALUE-1;
    int mid = (l+r)>>>1;
    System.out.println(mid);
    l=mid+1;
    mid = (l+r)>>>1;//  Using bit operations   Shift one bit to the right to avoid overflow 
    System.out.println(mid);
}

result

1073741823
1610612735

It can be seen that there is no overflow at this time

Method 2 It adopts the right shift operation in bit operation ¹, Is the most recommended way to write , Fast , Accurate result

05. Interview questions

1. There is an ordered table 1,5,8,11,19,22,31,35,40,45,48,49,50 When binary search 48 when The number of times to compare for a successful search is ?
2. Use binary search in sequence 1,4,6,7,15,33,39,50,64,75,78,81,89,96 When binary search 81 when It needs several comparisons ?
3. In a 128 Binary search for a number in an array of elements , The maximum number of times you need to compare

The first question is ：

It can be seen that this is basically the same as the example I gave at the beginning

for the first time our l=0 r=12, therefore mid=(l+r)/2=6 , here mid The element corresponding to the subscript is 31 Less than 48 So we make l=mid+1

The second time our l=7 r=12, therefore mid=(l+r)/2=9, here mid The element corresponding to the subscript is 45 Less than 48 So we make l=mid+1

The third time we l=10 r=12, therefore mid=(l+r)/2=11, here mid The element corresponding to the subscript is 49 Greater than 48 So we make r=mid-1

The fourth time we l=10 r=10, therefore mid=(l+r)/2=10, here mid The element corresponding to the subscript is 48 That is, the elements we need

Since then we have found elements 48 After four comparisons

The second question is basically the same as the first question So I'm not going to repeat it

Third question ：

Because the time complexity of binary search is $lo{g}_2^N$ , So the answer to this question is $lo{g}_{2}128$ be equal to 7

Be careful ： If $lo{g}_2^N$ The result of is not an integer Then round down +1

---

1. Shift right operation refers to the overall shift to the right by one bit in binary form , The overflow bit moves right into the high position , The lowest position is removed to the right , Complete the divide by two operation , But pay attention to ： Move right 1 Bits are not exactly equivalent to division 2, When it is positive, it is equivalent , Negative numbers are not equivalent ︎