[day 26] given the ascending array nums of n elements, find a function to find the subscript of target in nums | learn binary search

This article has been included in the column 《Java Introduction 100 cases 》

order 、 Column Preface

   This column opens , The purpose is to help everyone better master learning Java, Especially some Java Learners' It is difficult to find systematic algorithm learning materials on the Internet to help you get started with algorithms , At the same time, if you have any questions about the contents of the column, you can add my wechat at the end of the article to give you a one-to-one explanation .
   But the most important thing is to think independently , For all the content of this column , Be able to fully master , Write the code completely by yourself , There must be no problem getting started with the algorithm .
   The learning of algorithm must not be short of summary , Here I recommend that you can go to University algorithm community Punch in the learned knowledge , To consolidate and review .
   The only way to learn algorithms well must be Topic sea strategy , Only by accumulating a lot of practice can you practice your skills . Any topic of the column I will start with 【 Title Description 】【 Their thinking 】【 Template code 】【 Code parsing 】 Wait for four plates to explain .

order 、 Preface of this chapter

   Today's content is very important , The first involves binary search , This is a classic in a classic , The foundation in the foundation , But it is also an algorithm that can torture and kill a large number of people . Anywhere , It is a very important test site , Today we are just beginning to touch on .

Two points search

   Binary search is an optimization algorithm , It can usually $O(n)$ The search complexity is optimized to $O(logn)$. The premise of using binary search is that —— Dichotomy . Many people always have misunderstandings , Using binary search must have monotonicity , This view is wrong , Monotonicity is only one kind of the duality , It is the scene that we often encounter that can use dichotomy , In fact, if we satisfy the duality, we can divide into two .
   So what is Dichotomy Well ？

   For a range of data , There is a critical point , Make all the data on one side of the critical point satisfy a certain property , Neither side satisfies this property .

   Dichotomy has a core check function , The logic of this function is to find the properties of this critical condition , Make both sides satisfied , Neither side is satisfied . When our mid Fall on the interval satisfying the property , We will keep this point , When it falls on an unsatisfied interval , We'll round off the point , Finally, the left and right pointers will approach this critical point infinitely and exit the loop , We got the answer .

One 、【 Example 1】

1、 Title Description

   Given a n$(1\le n\le 10000)$ The elements are ordered （ Ascending ） integer array nums And a target value target , Write a function search nums Medium target, If the target value has a return subscript , Otherwise return to -1. Ensure that there are no duplicate elements in the array

2、 Their thinking

• $(1)$ Like the main core of binary search , Is to look for duality , For arrays with monotonicity, it is good to find the duality . Because the array is in ascending order , We know that for target The elements on the left must be less than target, about target The element on the right , Must be greater than or equal to target( This right side includes target The location of ), So we can find the duality .
• $(2)$ Combined with the above analysis , When mid Fall in a non-conforming range , We make l=mid+1, Because the non-conforming interval is on the left , When it falls in a consistent range , We make r=mid, Because the matching range is on the right , If... Exists in the array target, Then, when the cycle is over, it should meet nums[l]==nums[r]==target, Otherwise, there is no solution .

3、 Template code

class Solution {
    
    public int search(int[] nums, int target) {
    
        int n=nums.length;
        int l=0;
        int r=n-1;
        while(l<r){
    
            int mid=l+r>>1;
            if(nums[mid]>=target) r=mid;
            else l=mid+1;
        }
        return nums[r]==target?r:-1;
    }
}

4、 Code parsing

• $(1)$ Why is the cyclic condition written as l<r, instead of l<=r Well ？ because l<r The end condition of is l==r, here l and r In one position , We don't have to worry about the answer in the end l Up or r On , So it is recommended that everyone write this .
• $(2)$l+r>>1 What does that mean? ？>> Is the shift right operator , In essence, it will l+r Divide the sum of by 2, and (l+r)/2 No difference between , It's just >> A little faster . If l+r And may explode int, Should be written as r-l+l/2
• $(3)$ Finally, why should we judge nums[r]==target？ Although the array satisfies the duality , It does not mean target It must be in the array , For example, there are arrays $[1,2,4,5]$,target by 3 Under the circumstances , Arrays are also binary , But the critical point in the original array does not necessarily have an answer .
  

3、 ... and 、 Recommendation column

《 Zero fundamental algorithm 100 God 》

Four 、 After-school exercises

Serial number	Topic link	Difficulty rating
1	Two points search	2
1	Search insert location	2

There are questions about learning ？