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.

In JS, indexOf can be used directly:

var search = function(nums, target) {
    return nums.indexOf(target)
}
Copy the code

So, try implementing the JS indexOf method.

Method 1: The general solution is to iterate over the array, return subscript when it is present, and return -1 when the array is greater than that number when it is not present.

var search = function(nums, target) {
    for(let index = 0 ; index < nums.length; index++) {
        const num = nums[index]
        if (num === target) {
           return index
        } else if (num > target) {
            return -1
        }
    }
    return -1
}
Copy the code

Method two: dichotomy

Through diagrams and judgments, we can know the following steps that can save traversal:

1. When traversing the < target value on the left, there is no need to traverse the left element

2. There is no need to traverse the right element when traversing > target values

3. If conditions 1, 2 are met on both sides, -1 is returned

4. If no match is found on the left, -1 is returned

/** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function(nums, target) { let mid = Math.floor(nums.length / 2) let left = mid - 1 let right = mid + 1 if ( nums[mid] === target) { return mid } let isLeft = nums[left] >= target while((isLeft && left >= 0)) { if (nums[left] === target) { return left }  left-- } while(! isLeft && right <= nums.length) { if (right <= nums.length - 1 && nums[right] === target) { return right } right++ } return -1 };Copy the code