“🌟🌟🌟🌟🌟“

“Taste: Cumin beef“

“Cooking time: 5min“

This article has been featured on Github github.com/Geekhyt, thanks to Star.

The wine table once played such a small game, the rules of the game is: every time the host randomly choose a number from 1-1000, such as 171. Only the host know and write in advance on the note retention, and then respectively let everyone to guess, can use the least number of guess people win and have the right to designate a person to be punished.

  • Tong Oba: five hundred
  • Host: Big
  • Tong Oba: 250
  • Host: Big
  • Tong Oba: 125
  • Host: Small
  • Tong Oba: 187
  • Host: Big
  • Tong Oba: 156
  • Host: Small
  • Tong Oba: 171

Host again choose the number, let the garlic little sister to guess…

In the end, kid Oba used the least, kid Oba won! Designated grilled garlic little sister penalty wine.

The game is to see who can guess the host’s number the fewest times, the winner. This kind of lookup in an ordered set of data is perfect for binary lookup.

Binary Search

Binary search, as the name suggests. (See Oba’s skilled drinking operation above) Each search is to compare with the middle element of the interval, and reduce the interval to be searched by half until the target element is found, or the interval is reduced to 0 (not found). The time of binary search is order logn. Compared with constant time complexity, O(999999) is more efficient than O(1) when constant is large.

Although the binary algorithm is efficient, it also has some limitations. For binary lookup to work, there are several prerequisites that need to be met.

  • Order (monotonically increasing/decreasing)
  • Arrays (accessible by index)
  • The amount of data should not be too large (the array memory space is contiguous, the memory requirements are strict) nor too small (traversal is enough)

LeetCode bo

33. Search rotation sort array

Suppose the array sorted in ascending order is rotated at some previously unknown point.

For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].

Searches for a given target value, returning its index if it exists in the array, or -1 otherwise.

You can assume that there are no duplicate elements in the array.

Your algorithm must be order log n in time.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 output: -1

The key point

The rotated array must be partially ordered. Also, they’re asking for time order logn, which implies binary search.


Look at the rotated array as shown in the two cases above:

  • If nums[mid] >= nums[start], mid is in order 5 >= 2
  • When nums[mid] < nums[start], mid is on the right and the right is ordered 2 < 6

Then we decide which part of the target and discard the other part. As in the second case above, we assume that target is a black 3. Mid = mid (mid, end), target > nums[mid] && target <= nums[end], start = mid + 1)

const search = function(nums, target) {
    let start = 0;
    let end = nums.length - 1;
    
    while (start <= end) {
 const mid = start + ((end - start) >> 1);  if (nums[mid] === target) {  return mid;  }  // The left side is ordered  if (nums[mid] >= nums[start]) {  // Target is between [start, mid]  if (target >= nums[start] && target < nums[mid]) {  end = mid - 1;  } else {  start = mid + 1;  }  } else { // The right side is ordered  // Target between [mid, end]  if (target > nums[mid] && target <= nums[end]) {  start = mid + 1;  } else {  end = mid - 1;  }  }  }  return - 1; } Copy the code

Complexity analysis

  • Time complexity:O(logn)
  • Space complexity:O(1)You only need constant level space for variables

The articles

  • How the front end handles data structures and Algorithms (Pilot)
  • Time and space complexity analysis of JavaScript algorithm
  • Do you really understand recursion?
  • Divide and conquer, dynamic programming, backtracking, greed
  • The tree industry has a specialty

❤️ Love triple punch

1. Please give me a “like” when you see this. Your “like” is the motivation for my creation.

2. Pay attention to the front canteen of the public account, “your front canteen, remember to eat on time”!

3. This article has been included in the front canteen Github github.com/Geekhyt, for a small Star, thanks to Star.