LintCode 題解丨大廠算法面試模闆：二分查找

給定一個排序的整數數組（升序）和一個要查找的整數​target​，用​O(logn)​的時間查找到target第一次出現的下标（從0開始），如果target不存在于數組中，傳回​-1​。

線上評測位址：

LintCode 領扣

​

樣例 1:

輸入:[1,4,4,5,7,7,8,9,9,10]，1

輸出: 0

樣例解釋:

第一次出現在第0個位置。

樣例 2:

輸入: [1, 2, 3, 3, 4, 5, 10]，3

輸出: 2

第一次出現在第2個位置

樣例 3:

輸入: [1, 2, 3, 3, 4, 5, 10]，6

輸出: -1

沒有出現過6， 傳回-1

解題思路

題目提到，給定的數組已經排序，若從小到大周遊數組查找target，則時間複雜度為O(n)O(n)，n為數組長度。需要用一個O(logn)O(logn)的時間複雜度去完成本題，那麼需要用到二分查找。

二分查找常用于查找有序數組中目标數target的位置，用​left​和​right​記錄target所在的區間端點，每次将區間的中間位置值和target作比較，然後移動區間端點。

算法流程

将區間指派為整個數組區間（left = 0, right = n - 1），取中間位置mid

若​a[mid]​ < target，則将區間縮小到原區間的右區間(left = mid + 1)

若​a[mid]​ >= target，則将區間縮小至原區間的左區間(right = mid)

若left >= right 時，若​a[right]​ = target則傳回right, 否則傳回-1

複雜度分析

時間複雜度：O(logn)

每次查找都将區間縮小至原來長度的一半，可見查找的最多次數為logn

空間複雜度：O(1)

查找不需要開辟新的非常數級空間，隻需在原數組基礎上進行查找即可

代碼

public class Solution {

/**
 * @param nums: The integer array.
 * @param target: Target to find.
 * @return: The first position of target. Position starts from 0.
 */
public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int mid;

    while (left < right) {
        //得到中間位置
        mid = (right + left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    if (nums[right] == target) {
        return right;
    }

    return -1;
}           

}

更多題解參考：

九章算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時線上授課為你傳授面試技巧