大廠算法面試之leetcode精講5.二分查找

視頻教程（高效學習）:點擊學習

目錄：

1.開篇介紹

2.時間空間復雜度

3.動態(tài)規(guī)劃

4.貪心

5.二分查找

6.深度優(yōu)先&廣度優(yōu)先

7.雙指針

8.滑動窗口

9.位運算

10.遞歸&分治

11剪枝&回溯

12.堆

13.單調(diào)棧

14.排序算法

15.鏈表

16.set&map

17.棧

18.隊列

19.數(shù)組

20.字符串

21.樹

22.字典樹

23.并查集

24.其他類型題

二分搜索

時間復雜度O(logn)

步驟：

• 從數(shù)組中間的元素開始，如果中間的元素正好是目標值，搜索結(jié)束
• 如果目標值大于或小于中間的元素，則在大于或小于中間的元素的那一半繼續(xù)搜索

代碼模版

//二分查找偽代碼模版
while (left <= right) {
  mid = (left + right) / 2;
  if (array[mid] === target) return result;
  else if (array[mid] < target) left = mid + 1;
  else right = mid - 1;
}

704. 二分查找 （easy）

ds_119

方法1:遞歸

• 思路：先找到中間位置，判斷是否是需要尋找的目標值，如果是就返回，不是的話判斷目標值和中間元素的大小，然后繼續(xù)向左右子樹遞歸尋找
• 復雜度：時間復雜度O(logn)，空間復雜度O(logn)，遞歸棧大小

js：

var search = function (nums, target) {
    return search_interval(nums, target, 0, nums.length - 1)
};

function search_interval(nums, target, left, right) {
    if (left > right) {
        return -1
    }
    let mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) {//判斷目標值和中間元素的大小
        return mid
    } else if (nums[mid] < target) {//遞歸尋找目標元素
        return search_interval(nums, target, mid + 1, right)
    } else {
        return search_interval(nums, target, left, mid - 1)
    }
}

java：

class Solution {
    public int search(int[] nums, int target) {
        return search_interval(nums, 0, nums.length - 1, target);
    }
    private int search_interval(int[] nums, int l, int r, int target) {
        if (l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return search_interval(nums, l, mid - 1, target);
        } else {
            return search_interval(nums, mid + 1, r, target);
        }
    }
}

方法2:非遞歸

• 思路：定義left、right指針，比較目標元素和中間元素的大小，然后不斷縮小左右指針的范圍繼續(xù)尋找目標元素
• 復雜度：時間復雜度O(logn)，空間復雜度O(1)

js：

var search = function (nums, target) {
    let left = 0,
        right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (target < nums[mid]) {//比較目標和中間元素的大小，然后不斷縮小left和rihgt指針的范圍
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};

java：

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}

35. 搜索插入位置 (easy)

時間復雜度O(logn)，空間復雜度O(1)

js:

var searchInsert = function(nums, target) {
    const n = nums.length;
    let left = 0, right = n - 1, ans = n;
    while (left <= right) {
        let mid = ((right - left) >> 1) + left;
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
};

java:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

69. Sqrt(x)（easy）

方法1:二分法

• 思路：從0-x不斷二分，直到
• 復雜度分析：時間復雜度O(logx)，即為二分查找需要的次數(shù)。空間復雜度O(1)

js:

var mySqrt = function (x) {
    let left = 0
    let right = x
    while (left <= right) {
        let mid = left + ((right - left) >> 1)//中間位置索引 x>>1 表示除以2并取整，縮小一下遍歷的范圍
        if (mid * mid <= x) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right
};

Java:

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

方法2:牛頓迭代

• 思路：r = ( r + x / r ) / 2
• 復雜度分析：時間復雜度O(logx)?？臻g復雜度O(1)

js:

var mySqrt = function(x) {
    let r = x

    while (r ** 2 > x) r = ((r + x / r) / 2) | 0//取整

    return r
};

Java:

class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        double l = 0;
        double r = 1;
        while (l != r) {
            l = r;
            r = (r + x / r) / 2;
        }
        return (int)r;
    }
}

300. 最長遞增子序列 (medium)

動畫過大，點擊查看

方法1.動態(tài)規(guī)劃

• 思路：dp[i]表示選擇nums[i]，并且以nums[i]結(jié)尾的最長上升子序列的長度。兩層循環(huán)，i：1～nums.length，

  j：0～i，如果nums[i] > nums[j]，則構(gòu)成一個上升對，dp[i]就從dp[i], dp[j]+1兩個種選擇較大者，最后返回dp數(shù)組總的最大數(shù)

• 復雜度分析：時間復雜度O(n^2)，n是nums的長度，外層需要循環(huán)n次，dp[i]需要從dp[0~i-1],所以復雜度是O(n^2)?？臻g復雜度是O(n)，即dp數(shù)組的空間

js:

const lengthOfLIS = (nums) => {
    let dp = Array(nums.length).fill(1);
    let result = 1;

    for(let i = 1; i < nums.length; i++) {
        for(let j = 0; j < i; j++) {
            if(nums[i] > nums[j]) {//當nums[i] > nums[j]，則構(gòu)成一個上升對
                dp[i] = Math.max(dp[i], dp[j]+1);//更新dp[i]
            }
        }
        result = Math.max(result, dp[i]);//更新結(jié)果
    }

    return result;
};

Java:

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int result = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

方法2.二分查找+貪心

• 思路：準備tail數(shù)組存放最長上升子序列，核心思想就是越小的數(shù)字越要往前放，這樣后面就會有更多的數(shù)字可以加入tails數(shù)組。將nums中的數(shù)不斷加入tail，當nums中的元素比tail中的最后一個大時 可以放心push進tail，否則進行二分查找，讓比較小的數(shù)二分查找到合適的位置，讓后面有更多的數(shù)字與這個數(shù)形成上升子序列
• 復雜度：時間復雜度O(nlogn)，n為nums的長度，每次二分查找需要logn，所以是總體的復雜度是O(nlogn)?？臻g復雜度是O(n) ,tail數(shù)組的開銷

js:

var lengthOfLIS = function (nums) {
    let n = nums.length;
    if (n <= 1) {
        return n;
    }
    let tail = [nums[0]];//存放最長上升子序列數(shù)組
    for (let i = 0; i < n; i++) {
        if (nums[i] > tail[tail.length - 1]) {//當nums中的元素比tail中的最后一個大時 可以放心push進tail
            tail.push(nums[i]);
        } else {//否則進行二分查找
            let left = 0;
            let right = tail.length - 1;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (tail[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tail[left] = nums[i];//將nums[i]放置到合適的位置，此時前面的元素都比nums[i]小
        }
    }
    return tail.length;
};

Java:

class Solution {
    private int peek(){
        return tail.get(tail.size() - 1);
    }
    private ArrayList<Integer> tail;
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int last = nums[0];
        int max = 1;
        
        tail = new ArrayList<Integer>(len);
        tail.add(nums[0]);

        for(int i = 1 ; i < len ; ++i){
            if( nums[i] > peek() )
                tail.add(nums[i]);
            else{
                int l = 0, r = tail.size() - 1, mid = 0;
                while(l <= r){
                    mid = l + ((r - l) >> 1);
                    if( nums[i] > tail.get(mid) )
                         l = mid + 1;

                    else if( nums[i] < tail.get(mid) )
                         r = mid - 1;
                    else {l = mid; break;}
                 }
                 tail.set(l, nums[i]);

            }
        }
        
        return tail.size();
    }
}

4. 尋找兩個正序數(shù)組的中位數(shù) (hard)

方法1.二分查找

ds_87

• 思路：數(shù)組合并之后在排序的復雜度是O((m+n) log(m+n))不符合題意，題目要求的是O(log (m+n))，我們一看到logn的復雜度就聯(lián)想到了二分。二分長度較小的數(shù)組，找到這個數(shù)組二分的位置，在根據(jù)這個二分的位置和兩個數(shù)組的總長度找到另一個數(shù)組二分的位置，比較這兩個位置的四個數(shù)是否滿足交叉小于等于，不滿足繼續(xù)二分，滿足就找到了解
• 復雜度：時間復雜度O(log( min(m，n)) )，m、n分別是nums1和nums2的長度。每次二分循環(huán)的長度都會少一半，只要二分比較短的數(shù)組即可。空間復雜度O(1)

Js:

var findMedianSortedArrays = (nums1, nums2) => {
    let len1 = nums1.length, len2 = nums2.length
    if (len1 > len2) return findMedianSortedArrays(nums2, nums1)//對nums1和nums2中長度較小的二分
    let len = len1 + len2//總長
    let start = 0, end = len1 //進行二分的開始和結(jié)束位置
    let partLen1, partLen2

    while (start <= end) {
        partLen1 = (start + end) >> 1//nums1二分的位置
        partLen2 = ((len + 1) >> 1) - partLen1//nums2二分的位置

        //L1:nums1二分之后左邊的位置，L2，nums1二分之后右邊的位置
        //R1:nums2二分之后左邊的位置，R2，nums2二分之后右邊的位置

        //如果左邊沒字符了，就定義成-Infinity，讓所有數(shù)都大于它，否則就是nums1二分的位置左邊一個
        let L1 = partLen1 === 0 ? -Infinity : nums1[partLen1 - 1]
        //如果左邊沒字符了，就定義成-Infinity，讓所有數(shù)都大于它，否則就是nums2二分的位置左邊一個
        let L2 = partLen2 === 0 ? -Infinity : nums2[partLen2 - 1]
        //如果右邊沒字符了，就定義成Infinity，讓所有數(shù)都小于它，否則就是nums1二分的位置
        let R1 = partLen1 === len1 ? Infinity : nums1[partLen1]
        //如果右邊沒字符了，就定義成Infinity，讓所有數(shù)都小于它，否則就是nums1二分的位置
        let R2 = partLen2 === len2 ? Infinity : nums2[partLen2]

        if (L1 > R2) {//不符合交叉小于等于 繼續(xù)二分
            end = partLen1 - 1
        } else if (L2 > R1) {//不符合交叉小于等于 繼續(xù)二分
            start = partLen1 + 1
        } else { // L1 <= R2 && L2 <= R1 符合交叉小于等于
            return len % 2 === 0 ?
                (Math.max(L1, L2) + Math.min(R1, R2)) / 2 : //長度為偶數(shù)返回作左側(cè)較大者和右邊較小者和的一半
                Math.max(L1, L2)    //長度為奇數(shù)返回作左側(cè)較大者
        }
    }
}

Java:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m;
        int median1 = 0, median2 = 0;

        while (left <= right) {
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;
      
            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);

            if (nums_im1 <= nums_j) {
                median1 = Math.max(nums_im1, nums_jm1);
                median2 = Math.min(nums_i, nums_j);
                left = i + 1;
            } else {
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
}

162. 尋找峰值（medium）

ds_158

• 思路：題意nums[-1]、nums[n]都是-∞。所以數(shù)組中只要存在兩個相鄰元素是遞增的，那沿著它一定可以找到峰值
• 復雜度：時間復雜度O(logn)，空間復雜度O(1)

js：

const findPeakElement = nums => {
    let [left, right] = [0, nums.length - 1];
    while (left < right) {
        const mid = left + (right - left) >> 1;//不斷二分 尋找上升元素對
        if (nums[mid] > nums[mid + 1]) {
            right = mid;//下降
        } else {
            left = mid + 1;//上升
        }
    }
    return left;
};

java：

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        for (; left < right; ) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

74. 搜索二維矩陣 （medium）

• 思路:矩陣從左到右 從上到下滿足遞增的性質(zhì)，所以可以把二維數(shù)組看成一個一維遞增的數(shù)組，然后進行二分查找，只需要將一位坐標轉(zhuǎn)換成二維坐標。
• 復雜度:時間復雜度O(log(mn))，m，n是矩陣的行和列。空間內(nèi)復雜度O(1)

js：

var searchMatrix = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let low = 0, high = m * n - 1;
    while (low <= high) {
        const mid = Math.floor((high - low) / 2) + low;
        const x = matrix[Math.floor(mid / n)][mid % n];//一維坐標轉(zhuǎn)換成二維坐標
        if (x < target) {
            low = mid + 1;
        } else if (x > target) {
            high = mid - 1;
        } else {
            return true;
        }
    }
    return false;
};

java：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

34. 在排序數(shù)組中查找元素的第一個和最后一個位置 （medium）

方法1:先二分，在尋找左右邊界

• 思路：二分查找，然后向左和向右嘗試找相同的元素
• 復雜度：時間復雜度O(n)，空間復雜度O(1)

js：

//nums = [5,7,7,8,8,10], target = 8
var searchRange = function(nums, target) {
    let left = 0, right = nums.length - 1, mid;
    while (left <= right) {//二分查找target
        mid = (left + right) >> 1;
        if (nums[mid] === target) break;
        if (nums[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    if(left > right) return [-1, -1];
    let i = mid, j = mid;
    while(nums[i] === nums[i - 1]) i--;//向左嘗試找相同的元素
    while(nums[j] === nums[j + 1]) j++;//向右嘗試找相同的元素
    return [i, j];
};

java：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

方法2：改造二分法

• 思路：改造二分，尋找目標值的開始和結(jié)束位置
• 復雜度：時間復雜度O(logn)，空間復雜度O(1)

js：

//nums = [5,7,7,8,8,10], target = 8
const binarySearch = (nums, target, lower) => {
    let left = 0, right = nums.length - 1, ans = nums.length;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
            right = mid - 1;
            ans = mid;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

var searchRange = function(nums, target) {
    let ans = [-1, -1];
    const leftIdx = binarySearch(nums, target, true);
    const rightIdx = binarySearch(nums, target, false) - 1;
    if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] === target && nums[rightIdx] === target) {
        ans = [leftIdx, rightIdx];
    } 
    return ans;
};

java：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 (medium)

ds_176

• 思路：low和high指針不斷向中間移動，不斷二分，當前節(jié)點比high節(jié)點的值小，讓high等于pivot，當前節(jié)點比大于等于high節(jié)點的時候，讓low等于pivot+1，最后相遇的節(jié)點就是最小值
• 復雜度：時間復雜度O(logn)?？臻g復雜度O(1)

js：

var findMin = function(nums) {
    let low = 0;
    let high = nums.length - 1;
    while (low < high) {
        const pivot = low + Math.floor((high - low) / 2);//中間節(jié)點
        if (nums[pivot] < nums[high]) {//當前節(jié)點比high節(jié)點的值小，讓high等于pivot
            high = pivot;
        } else {
            low = pivot + 1;//當前節(jié)點比大于等于high節(jié)點的時候，讓low等于pivot+1
        }
    }
    return nums[low];//最后相遇的節(jié)點就是最小值
};

java：

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
}

374. 猜數(shù)字大小 (easy)

• 復雜度：時間復雜度O(logn)。空間復雜度O(1)

js:

var guessNumber = function(n) {
    let left = 1, right = n;
    while (left < right) { 
        const mid = Math.floor(left + (right - left) / 2); 
        if (guess(mid) <= 0) {
            right = mid; //更新查找區(qū)間為[left, mid]
        } else {
            left = mid + 1; //更新查找區(qū)間為[mid+1, right]
        }
    }
    //left == right為答案
    return left;
};

java:

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2; 
            if (guess(mid) <= 0) {
                right = mid;
            } else {
                left = mid + 1; 
            }
        }
        return left;
    }
}