This is the third day of my participation in the August More Text Challenge

Binary search basis

Binary search can be used in many scenarios, such as operating systems, MySQL, Hadoop, etc

  • Finds the given data in the ordered array A. The data set of the operation is ordered
  • Binary search can be applied to any type of data. The collection of search is a relatively static data set

The interview questions

Topic 1: Finding a target value in an ordered array

Ary = [1, 3, 4, 9, 11, 15, 19, 20,25], target = 8 use binary search to determine whether there is a target value.

Their thinking

Binary search, an ordered set of data is split in half, and the middle elements of each partition are examined, repeating the loop until there is no range. This range is controlled by two variables, left and right.

First, define an interval [left, right] (left: head position, right: tail position) open and close principle, the data we need to locate is within this range

Round 1:1, 3, 4, 9, 11, 15, 19, 20 25 left=0, right=8, mid=4

Ary [mid] > target, right = mid-1=3

Round 2:1, 3, 4, 9, 11, 15, 19, 20 left =0 right = 3, mid= 1

Ary [mid] <target, left = mid+1 = 2

Round 3:1, 3, 4, 9, 11, 15, 19, 20 25 left =2 right = 3 mid=2

Left moves from left to right, right from right to left. [Fixed] Once the target is found in the middle, the search stops. If no target is found, left and right overlap.

JavaScript implementation

function erfenSearch(ary, target) {
    if (ary.length ==0) return false;
​
    let left = 0, right = ary.length;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if(ary[mid] == target){
            return true;
        } else if (ary[mid] > target) {
            right = mid - 1;
        } else  if (ary[mid] < target)  {
            left = mid + 1;
        }
​
    }
    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).

Title 2: Find the smallest element of a rotated array (with duplicates)

The rotation array of 1, 2, 3, 4, 5 is: 3, 4, 5, 1, 2 to find the smallest element in the array

Answer:

The query length is reduced by setting three flag bits left, right and mid. Define 3, 4 and 5 as the primordial sequence; 1,2 are flipped subsequences.

If the middle element ary[mid] is less than the left element ary[left], it is proved that the middle element belongs to the flipped subsequence. In this case, the minimum element exists between the marker bit [left,mid); similarly, when the middle element is larger than the left element, the minimum element exists directly in the marker bit [mid,right].

JavaScript implementation

Function findMin(ary) {let len = ary.length; if(len == 0) return -1; let left = 0, right = len - 1, mid; while(left < right){ mid = left + (right - left) / 2; if(ary[mid] > ary[right]) left = mid + 1; else if(ary[mid] < ary[right]) right = mid; else right--; } return ary[left]; }Copy the code