Leetcode:704 binary search

Brush slowly today leetcode 了 , Follow the online Daniel's question brushing route step by step , The specific route is ： Array -> Linked list -> Hashtable -> character string -> Stack and queue -> Trees -> to flash back -> greedy -> Dynamic programming -> graph theory -> Advanced data structure

The first step is ： Array

Relevant theoretical basis

1、 An array is a collection of the same type of data stored in continuous memory space .

2、 Array subscripts are all from 0 At the beginning , The address of array memory space is continuous

         When we delete or add elements , It's hard to avoid moving the addresses of other elements

3、c++ The two-dimensional array is continuous in the address space , and JAVA It is not

Title Description ： Given a  n  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

  Their thinking ：

1、 The premise of binary search ：1 Ordered array ,2 There are no duplicate elements in the array

2、 Binary search method involves interval range 、 The boundary conditions . To be clear about the definition of interval , The boundary conditions are treated according to the definition of interval

3、 Use two interval methods to solve problems ： Left and right closed , Left closed right away

Method 1 ： Left and right closed , That is to say [left, right] 

The main points of ：

• while (left <= right) To use <= , because left == right It makes sense , So use <=
• if (nums[middle] > target) ：right To assign as middle - 1, Because of the current nums[middle] It must not be target, Then the end subscript position of the left interval to be found next is middle - 1

Specific code implementation

//  Version of a 
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; //  Definition target In a left closed right closed interval ,[left, right]
        while (left <= right) { //  When left==right, Section [left, right] Is still valid , So use  <=
            int middle = left + ((right - left) / 2);//  Prevent overflow   Equate to (left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target  In the left range , therefore [left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target  In the right range , therefore [middle + 1, right]
            } else { // nums[middle] == target
                return middle; //  Target value found in array , Return the subscript directly 
            }
        }
        //  Target value not found 
        return -1;
    }
};

Method 2 ： Left close right open, that is [left, right) 

The main points of ：

• while (left < right), Use here < , because left == right In the interval [left, right) It doesn't make sense
• if (nums[middle] > target) right Updated to middle, Because the current nums[middle] It's not equal to target, Go to the left section and keep looking , The search interval is left closed and right open , therefore right Updated to middle, namely ： The next query interval will not be compared nums[middle]

Specific code implementation

//  Version 2 
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); //  Definition target In the interval between left closed and right open , namely ：[left, right)
        while (left < right) { //  because left == right When , stay [left, right) It's invalid space , So use  <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target  In the left range , stay [left, middle) in 
            } else if (nums[middle] < target) {
                left = middle + 1; // target  In the right range , stay [middle + 1, right) in 
            } else { // nums[middle] == target
                return middle; //  Target value found in array , Return the subscript directly 
            }
        }
        //  Target value not found 
        return -1;
    }
};

summary ：

1、 The most important thing about binary search is to define the interval you define , Deal with the boundary conditions according to the defined interval