This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

Today I bought a convertible bond with a yield of 30%+. Now in this market, convertible bonds are still a bent over to pick up copper, as long as you are willing to buy every day, every year or a few, and accidentally, like today, the rise of 30%, is not a chicken leg. Next time looking for an opportunity to do A convertible bond to share, suitable as A share of the novice project. I came back late in the evening. I was always busy on Monday, so I hurried to finish the problem and write the article after coming back. Today, I will continue to do problem 34 of Leetcode.

The title

Given an array of integers in ascending order, nums, and a target value, target. Find the starting and ending positions of the given target value in the array.

If no target value exists in the array, return [-1, -1].

Advanced: Can you design and implement an O(log n) time complexity algorithm to solve this problem?

 

Example 1: input: nums = [5,7,7,8,8,10], target = 8 output: [3,4]

Example 2: input: nums = [5,7,7,8,8,10], target = 6 output: [-1,-1]

Example 3: Input: nums = [], target = 0 Output: [-1,-1]

 

0 <= nums.length <= 105-109 <= nums[I] <= 109

Train of thought

At first glance, isn’t this a binary search? Unlike the basic binary search, the same value may appear many times, which is a variation of the ordinary binary search. This is similar to yesterday’s problem, where we added a little change to the basic binary search. Where is the target starting position and the end position? So we want to figure out the indices of target on the left and target on the right. Normal binary search, we find target and we’re done, and the method returns, and if we want to find the index of the leftmost target, which we can’t range yet, because the left might still be there, we just write down the current index, and then we go to the left and continue to do binary search until we find the leftmost target, and of course, Same thing for target on the far right. Left = 0, right = 4, mid = 2, left = 0, right = 4, mid = 2, left = 0, right = 4, mid = 2 Continue with binary search until you find the leftmost 2 with a subscript of 1; If num[mid] = target, left = mid

  • 1 Continue searching.

Java version code

class Solution { public int[] searchRange(int[] nums, int target) { int[] ans = new int[2]; ans[0] = searchRange(nums, target, true); ans[1] = searchRange(nums, target, false); return ans; } /** * find the left and right boundaries of the elements in the sorted array, isLeft is true is the left boundary, @param target * @param isLeft * @return */ public static int searchRange(int[] nums, int target, boolean isLeft) { int len = nums.length; int ans = -1, left = 0, right = len - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { ans = mid; if (isLeft) { right = mid - 1; } else { left = mid + 1; } } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return ans; }}Copy the code