This is the 21st day of my participation in the August Text Challenge.More challenges in August

🐳 algorithm problem

The integer array NUMs is sorted in ascending order, with different values in the array.

Before passing to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,5,6,7 [0], for example, in the subscript 3 after rotation may become,5,6,7,0,1,2 [4].

Give you the rotated array nums and an integer target, return its subscript if nums contains the target value, otherwise -1.

Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4Copy the code
Example 2: input: nums = [4,5,6,7,0,1,2], target = 3 output: -1Copy the code
Example 3: Input: nums = [1], target = 0 Output: -1Copy the code
Tip: 1 <= nums.length <= 5000-10 ^4 <= nums[I] <= 10^4 Each value in NUMs is unique Advanced: Can you design a solution with order (log n) time complexity?Copy the code

🐳 A little thought

When I first did this problem I thought it was a rotation array but I didn’t know it was a rotation array, but I just wanted to check the coordinates. Ok, let’s summarize the common search algorithms:

  • Binary search
  • Binary tree lookup
  • Hash table

So let’s do a simpler binary search.

🐳 source code and analysis

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        
        int l = 0, r = n - 1;
        while (l <= r) {
        // Dichotomous souls find intermediate coordinates
            int mid = (l + r) / 2;
            // It was pure luck
            if (nums[mid] == target) {
                return mid;
            }
            For example, [4,5,6,7,0,1,2] rotates the array in ascending order
            // The result of this judgment can indicate whether the order is always ascending from the beginning to the middle
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;// Move the right pointer
                } else {
                    l = mid + 1;// Move the left pointer}}else {// Same thing
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1; }}}return -1; }}Copy the code

🐳 interview questions

What is the difference between CPU utilization and CPU load

When it comes to CPU utilization, you must understand time slices. What is a CPU time slice? Today’s Windows, Linux, and Mac OS are all “multitasking operating systems,” meaning they can run multiple programs “simultaneously,” for example, browsing the Web with Chrome and listening to music at the same time.

But how does an operating system achieve multitasking when, in fact, a CPU core can only do one thing at a time? The approximate approach is to have multiple processes take turns using the CPU for a short period of time. Since this “short period” is so short (between 5ms and 800ms on Linux), the user does not feel it, as if several programs are running at the same time. The “small amount of time” mentioned above is what we call a CPU time slice, and modern time-sharing multi-tasking operating systems use cpus in time slices.

The CPU usage is the application’s usage of the CPU time slice, that is, THE CPU usage = the application’s usage of the CPU time slice/the total time. For example, if process A occupies 10ms, process B occupies 30ms, and then process B is idle for 60ms, then process A occupies 10ms, and process B occupies 30ms, and then process B is idle for 60ms, then the CPU usage during this period of time is 40%. CPU utilization shows the percentage of CPU that the program uses in real time during runtime.

The CPU usage of most operating systems is classified into user CPU usage and system CPU usage. User-mode CPU usage is the percentage of total CPU time spent executing application code. System-state CPU usage, by contrast, is the percentage of total CPU time that an application spends executing operating system calls. High CPU utilization in the system state means contention for shared resources or a lot of interaction between I/O devices.

The CPU load shows the average number of tasks in use and waiting to use the CPU over a period of time.

One is the real-time CPU usage, and the other is the current and future CPU usage. For example, if I have a program that uses the CPU all the time, the CPU usage may be 100%, but the CPU workload is close to “1” because the CPU only does one job. What if you run both of these programs at the same time? The CPU utilization is still 100%, but the workload is 2. In other words, a higher CPU workload means that the CPU must switch between different tasks frequently. Whether CPU utilization is high or low does not necessarily depend on how many tasks are queued later (CPU load).

For a single-core CPU, a load of 1 indicates that the CPU has reached its full load state. If the load exceeds 1, subsequent processes need to queue for processing. If it’s multi-core, multi-CPU, let’s say the server now has 2 cpus, and each CPU has 2 cores, then the total load is no more than 4.

You can run the uptime and w commands to view the average CPU load. In addition, you can run the top command to view the total CPU usage and CPU usage of each process.