Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card for the 16th day 🎈!
🚀 Algorithm 🚀

🌲 Example of original problem

Given a sorted array and a target value, find the target value in the array and return its index.

If the target value does not exist in the array, return the position where it will be inserted in order.

You must use an O(log n) time complexity algorithm.

The sample1: Input: nums = [1.3.5.6], target = 5Output:2
Copy the code
The sample2: Input: nums = [1.3.5.6], target = 2Output:1
Copy the code
The sample3: Input: nums = [1.3.5.6], target = 7Output:4
Copy the code
The sample4: Input: nums = [1.3.5.6], target = 0Output:0
Copy the code
The sample5: Input: nums = [1], target = 0Output:0
Copy the code

Tip:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • Nums is an ascending array of non-repeating elements
  • -104 <= target <= 104

🌻C# method 1: common law

StrStr () returns an index given a target value. StrStr () returns an index given a target value

But this is looking up from an array, the last one was a string!

Let’s look at four possible scenarios

  • nums[i]==target
  • nums[i]>target
  • nums[0]>target
  • nums[nums.Length-1]<target

If (nums[I] >= target) return I; Return nums.Length;

Code:

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        for(int i = 0; i < nums.Length; i++)
        {
            if(nums[i] >= target) return i;
        }
        returnnums.Length; }}Copy the code

The execution result

By execution time:76Ms, in all CBeat 99.07% of users in # submissionsMemory consumption:24.7MB, in all CBeat 44.39% of users in # submission
Copy the code

Complexity analysis

Time complexity: O(longN) Space complexity: O(1)
Copy the code

🌻C# method two: dichotomy

Code:

public class Solution {
    public int SearchInsert(int[] nums, int target)
    {
        int low = 0;
        int high = nums.Length - 1;
        int mid = 0;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (target == nums[mid]) return mid;
            else if (target > nums[mid]) low = mid + 1;
            else high = mid - 1;
        }
        // This is the conventional dichotomy

        if (target > nums[mid]) return mid + 1;
        else returnmid; }}Copy the code

The execution result

By execution time:76Ms, in all CBeat 99.07% of users in # submissionsMemory consumption:24.5MB, in all CBeat 84.00% of users in # submission
Copy the code

🌻Java method 1: binary

Code:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l=0,r=n-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]<target)
                l=mid+1;
            else r=mid-1;
        }
        returnl; }};Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100% user memory consumption:37.8MB, beat out all Java commits87.55% of the userCopy the code

Complexity analysis

Time complexity: O(longN) Space complexity: O((1)
Copy the code

💬 summary

  • Today is the 16th day of the buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!