Binary search & the version of the first error

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Today we come to a binary search problem, in fact, binary search principle is very simple, but in the implementation of the code, need to consider a lot of boundary cases, want to write binary search once, or need to practice a practice ~ this problem I met in [nio] side of ~

Binary Search is also called Binary Search, which is a highly efficient Search method. However, split lookup requires that the linear table must have a sequential storage structure, and the elements in the table are ordered by keywords.

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.

Source: LeetCode link: leetcode-cn.com/problems/bi…

【 句 型 操 练 】 Head and tail pointer

Binary search is to start from both ends of the pointer, repeated half, narrowing the search area, until the Pointers overlap

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var search = function(nums, target) {
    let i = 0;
    let j = nums.length - 1;
    
    while(i <= j){
        // The advantage of this addition is to prevent I +j from being too large, which is a common technique
        let index = Math.floor(i + (j-i)/2);
        
        if(nums[index] === target){
            return index;
        }else if (nums[index] < target){
            i = index + 1;
        }else{
            j = index - 1; }}return -1;
};
Copy the code

278. The first incorrect version

You are a product manager, currently leading a team to develop a new product. Unfortunately, the latest version of your product did not pass the quality test. Since each version is based on the previous version, all versions after the incorrect version are incorrect. Suppose you have n versions [1, 2… n] and you want to find the first incorrect version that causes all subsequent versions to fail.

Source: LeetCode link: leetcode-cn.com/problems/fi…

Binary search

Binary search, notice the boundary case here

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/ * * *@param {function} isBadVersion()
 * @return {function}* /
var solution = function(isBadVersion) {
    / * * *@param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let i = 1;
        let j = n;
        while(i < j){
            let mid = Math.floor(i + (j-i)/2);
            if(isBadVersion(mid)){
                j = mid;
            }else{
                i = mid + 1; }}return i;
    };
};
Copy the code