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

Binary search

Binary search has many applications in engineering, such as operating system, MySQL, Hadoop, And Spark. Binary search is used when searching data.

Binary search basis

The purpose of binary search is to find A given number in an ordered array A. Let’s say we want to find target=3 in the array below.

Let’s examine this code

boolean binarySearch(long[] A, long target) {
  if (A == null || A.length == 0) {
    return false;
  }
  // Set the initial interval, here we use the open closed principle [l, r]
  int l = 0, r = A.length;
  // If the entire interval is empty, the loop is finished.
  // We use the open closed principle to represent an interval, so when l < r
  // The interval we are looking for is not an empty interval yet.
  while (l < r) {
    final int m = l + ((r - l) >> 1);
    if (A[m] == target) {
      return true;
    }
    if (A[m] < target) {
      // If the center point is smaller than the target value, the left part needs to be thrown away. The [l, m]
      // This interval is discarded, since we use the open and close principle, so the new interval needs to be
      // [m + 1, r]
      l = m + 1;
    } else {
      // If the midpoint is larger than the target value, the right part should be thrown away, i.e. [m, r].
      // Then the new interval becomes [l, m]. Since we use the open close principle,
      // just set r = m.r = m; }}return false;
}
Copy the code

Complexity analysis: In binary lookup, since we throw away half of the data each time, the total time complexity is O(LGN), and the space complexity is O(1).

summary

Binary search is a very basic topic, but as an interviewer, I’ve seen a lot of candidates fall for it. Therefore, I need to highlight a few key points in binary search.

  1. The open and closed principle, the open and closed principle is a representation of an interval. It’s important to note that when you write binary search, each interval is represented strictly on and off. This is a very important question to ask in an interview (knock on the blackboard, several companies I’ve worked for like to check out).
  2. The change of the interval should be deeply understood in three cases:
    1. Throw away why the left interval is L = M + 1, throw away why the right interval is R = M;
    2. Why does an L increment by 1 and an R increment by 1;
    3. Why the conditions for the loop need to be L < R.
  3. Code fluency is a very, very basic algorithm. If you’re stuck writing code, I suggest you ask two questions:
    1. Is it true that deep understanding of the open and closed principle in binary search inside the embodiment?
    2. Do you really remember this code template?