“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

Topic:

Binary search

Given an ordered (ascending) integer array nums with n elements and a target value, write a function to search for target in NUMs, returning a subscript if the target value exists, and -1 otherwise.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Interpretation: 9 appears in nums with subscript 4Copy the code

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Description: 2 does not exist in NUMs so -1 is returnedCopy the code

 

Tip:

  1. You can assume thatnumsNone of the elements in.
  2. nWill be in[1, 10000]In between.
  3. numsEach element of the[- 9999, 9999]In between.

Ideas:

  1. In an ordered array, we can split it in half every time
  2. Find the length of the arrayn
  3. Take the left edge of the arrayleft = 0And right boundaryright = n - 1
  4. throughwhileLoop, each time to determine whether the boundary moves left or right

Demo: Find 8 in the following array

[2, 4, 6, 8, 10]

left = 0; right = 4;

Compare the middle bit of the array with 8. If 6 < 8, the left boundary moves to the right

left = 2; right = 4;

After round 1: [6, 8, 10]

If the middle digit of the array is equal to 8, return it

Implementation:

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
 var search = function (nums, target) {
  let left = 0;
  let right = nums.length;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    // If found, return directly; if not found, return directly
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1; }}// No one is found
  return -1;
};
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.