This is the 17th day of my participation in Gwen Challenge

Example: the leftmost element in an ordered array

The title

Given an ordered array, returns the leftmost position of the specified element in the array

Input: A = [1, 2, 2, 2, 2, 3, 3], target = 2

Output: 1.

Explanation: The first occurrence of 2 is at subscript 1, the position where the first occurrence of 2 occurs when viewed from left to right.

I have come across this problem in telephone calls from many companies. It’s actually not that hard, it’s essentially a template problem, and it’s the basis for us to solve subsequent problems, and you need to really understand and memorize the code. Otherwise your binary search is “building towers on sand”.

There may be variations on this question, such as: “Find the first occurrence of 2 in an ordered array”, or “Find the last occurrence of 2 in an ordered array”.

An incorrect answer is: “Use the dichotomy to find a 2, then search left and right.” But then the time is order N.

So is there a way to reduce complexity? So let’s take a look at how to find the leftmost element based on binary search. So let’s do a simulation.

Analysis of the

1. The simulation

Let’s simulate an example by using dichotomies on paper or in our heads.

Law of 2.

It can be concluded that the purpose has become: to find a final segmentation point L, all elements in the interval [0, L) must be smaller than target, and all elements to the right of [L, ~) must be >= target. The operation principle of the left boundary is as follows:

  • The search interval is always a left-open and right-closed interval [L, R];
  • Always discard the range >= target, and set R = M;
  • When the last interval element is less than target, move L, no less than target, and set L = M + 1.

It can be summed up as “neither this nor that.”

So when the program is finally executed, L must be in one of the following situations.

If a target is present in an ordered array, the leftmost target must be found.

If there is no target in the ordered array, then:

  1. If all elements in the array are smaller than target and L refers to the length of the array, access to A[L] is illegal.
  2. Otherwise, A[L] must > target.

It can be summed up as “either out of bounds or greater than or equal to target”.

3. The matching

And if you look a little bit more carefully, you can see that in binary search here, compared to traditional binary search, we just get rid of the following condition, and finally we can get the L to the right place.

if (A[m] == target) {
  return true;
}
Copy the code

4. The boundary

There are actually several more boundary cases to discuss:

  • An empty array, or an array of length 0;
  • The elements in the array are all less than target;
  • All elements in the array are greater than target;
  • The elements in the array can be large or small, but the target does not exist in it.
  • An element in an array has only one target.

All of these boundaries are important.

Suggestion: In real interviews, many people write binary search code, often stuck in the above several boundaries. So it’s a plus to take the initiative to write test cases after you’ve written code during the interview.

Template code one: lowerBound

int lowerBound(long[] A, int n, long target) {
  int l = 0, r = n;
  while (l < r) {
    final int m = l + ((r - l) >> 1);
    if (A[m] < target) {
      l = m + 1;
    } else{ r = m; }}return l;
}
Copy the code

Complexity analysis: We always use binary search to go straight to the target solution. Therefore, the time complexity of the algorithm is O(LGN) and the space complexity is O(1).

summary

The code is short, but it’s easy to get this code wrong.

Interview research points:

  • When does the loop end? (Corresponding to line 3 of code)
  • When is the left boundary updated? How is it updated? (Corresponding to lines 5~6 of code)
  • When is the right boundary updated? How is it updated? (Corresponding to lines 7~8 of code)

The essence of all these problems can be boiled down to one knowledge point: the open and close principle.

Deformation and extension

If we have lowerBound, we can use the lowerBound function to write our new binarySearch algorithm.

boolean binarySearch(long[] A, int n, long target) {
  int l = lowerBound(A, n, target);
  return l < n && A[l] == target;
}
Copy the code

In fact, the binary_search function in the C++ STL library is implemented this way.

The title

UpperBound is a function that finds the upperBound of a given element in an array. Notice that the upper bound is the location of the element that is just larger than target. For example, if A = [1, 1, 100, 100] and target = 1, upperBound should return subscript 2.

Analysis of the

UpperBound finds a point y where we cut:

  • All elements in the left interval [0, y] <= target
  • Target < all elements in the right range of [y, ~)

Based on upperBound’s goals, we need to adjust the binary strategy:

  • When A[M] <= target, drop the [L, M] interval. Set L = M + 1.
  • When A[M] > target, drop the (M, R) range. You need to set R = M.

Template code two upperBound

int upperBound(long[] A, int n, long target) {
  int l = 0, r = n;
  while (l < r) {
    final int m = l + ((r - l) >> 1);
    if (A[m] <= target) {
      l = m + 1;
    } else{ r = m; }}return l;
}
Copy the code

summary

So far, we have harvested two template codes:

  • LowerBound, which can be used in conjunction with binarySearch;
  • UpperBound.

Important: Understand and memorize these two template codes before preparing for the interview. Here’s a trick: lowerBound and upperBound code are exactly the same. The only difference is when A[m] is compared with target:

  • LowerBound is A[m] < target
  • UpperBound is A[m] <= target

You can also look at which side you want to leave when A[m] == target.