[leetcode] 8. binary search · binary search

Title Description

Description in English

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

English address

https://leetcode.com/problems/binary-search/

Description of Chinese version

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.

Example 1: Input : nums = [-1,0,3,5,9,12], target = 9 Output : 4 explain : 9 Appear in the nums And the subscript is 4

Example 2: Input : nums = [-1,0,3,5,9,12], target = 2 Output : -1 explain : 2 non-existent nums So back to -1

Tips ：

• You can assume nums All elements in are not repeated .

• n Will be in [1, 10000] Between .

• nums Each element of will be in [-9999, 9999] Between .

Address of Chinese version

https://leetcode.cn/problems/binary-search/

Their thinking

Comprehensive topic requirements , Consider using recursive methods . Specific steps ：

1. Determine the length of the array and get the median subscript （ The method of taking the median value with odd length is different from that with even length ）

2. Compare the array value of this subscript with the target value （ There will be three situations , Treat separately ）

   1. equal ： Directly return the subscript , Program end

   2. The array value of this subscript > The target ： Take the data of the first half of the array and continue from step 1 Start comparing

   3. The array value of this subscript < The target ： Take the data of the second half of the array and continue from step 1 Start comparing

3. There must be only one value left in the end , Equal returns the subscript , Unequal return -1

How to solve the problem

My version

class Solution {
   public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        return getValue(start, end, target, nums);
    }

    public int getValue(int start, int end, int target, int[] nums) {
       // length Length  index Indicates subscript 
        int length = end - start + 1;
        int index = 0;
        if (length < 1) {
            return -1;
        } else {
            if (length % 2 != 0) {
                //  With median  3/2=1
                index = length / 2 + start;
            } else {
                //  No median , Take the first one at the beginning of the second half 
                index = length / 2 + start;
            }

            if (nums[index] == target) {
                return index;
            } else {
                if (nums[index] < target) {
                    start = index + 1;
                    if ((end - start) >= 0) {
                        return getValue(start, end, target, nums);
                    } else {
                        return -1;
                    }
                } else {
                    end = index - 1;
                    if ((end - start) >= 0) {
                        return getValue(start, end, target, nums);
                    } else {
                        return -1;
                    }
                }
            }
        }
    }
}

Official edition

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

Complexity analysis

• Time complexity ：O(logn) among n Is array length

• Spatial complexity ：O(1)

summary

In general , The first thought is probably violent enumeration , But in fact, many violent enumerations have a lot of double counting , Our optimization idea is actually space for time , Consider whether the processed results can be stored in the set , Traverse to the same node , You can directly look up the table to get .

The code of the official version is much simpler ,while Cycle is really a good choice without knowing the number of cycles （ Be sure to set the exit ）, Obviously , The official method is iterative , I think I use recursive method , This raises my question about the difference between iteration and recursion ？ This question raises questions , Although my code creates a new function , This function has its own situation of calling itself , It does seem recursive , But my previous understanding of recursion is like “ Dolls ” Recursive functions solve the smallest problem that can no longer be decomposed , But the array I pass here is actually the original one , Only by updating the start value and end value to continuously narrow the range of the array , It feels more like an iteration in the form of recursion (◎_◎;), Then I'm a little hooded ... Students who hope to distinguish clearly point out one or two （ Huai Quan .gif）