This is question of the Day from LeetCode 2021-9-6: “704. binary Search”

1. Topic description

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

2. Answer

Binary search classic example.

  1. Define the left and right indexes
  2. Get the median
  3. If the median value is greater than the target value, it is on the left and the right index needs to be changed
  4. If the median value is less than the target value, the left index needs to be changed on the right
  5. The intermediate value equals the target value and returns the intermediate index directly
  6. At the end of the walk, if you haven’t found it, return- 1
const search = (nums, target) = > {
    // Define the left and right indexes
    let [low, high] = [0, nums.length - 1];
    while (low <= high) {
        // mid is an intermediate index
        const mid = (low + high) >> 1;
        / / intermediate value
        const item = nums[mid];
        if (item > target) {
            // If the median value is greater than the target value, it is on the left
            high = mid - 1;
        } else if (item < target) {
            // If the median value is less than the target value, it is on the right
            low = mid + 1;
        } else {
            returnmid; }}return -1;
};
Copy the code

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”