基本款

给定一个长度为n的整数数组。请在数组中查找整数t，输出它的位置，不存在输出-1。 这个数组并没有特别的性质，我们只能从第一个数开始遍历去查找t的位置，显然时间复杂度O(n)。

二分

加一条件：数组有序。为了简化，我们设置数组中没有重复的数。 举个例子：加入我们要在下面这个数组中找3，我们可以先找到整个数组的中点，是6，3<6，所以3一定出现在6的左侧。 我们可以瞬间将搜索范围缩小到原来的一半。每次砍一半，时间复杂度是。

1 3  6  8 9
    👆🏻mid

查找函数实现

int find(int t) {      // 查找的目标数为t
    int l = 1, r = n;  // 初始化查找范围为[1, n]
    while (l <= r) {   // 搜索范围不为空，我们用闭区间来思考，l == r时，搜索范围还是有一个数的
        int mid = l + (r - l) / 2;   // 使用左端点+长度的一半计算中点。 因为(l + r) / 2中l + r可能会超过int范围。
        if (t == a[mid]) return mid; // 找到t，直接返回下标。
        if (t > a[mid]) l = mid + 1; // 目标数t大于中点数，去中点的右侧继续查找。改左指针。
        if (t < a[mid]) r = mid - 1; // 目标数t小于中点数，去中点的左侧继续查找。改右指针。
    }
    return -1; // 若未找到，返回-1。
}

豪华款

数组中有重复的数，我们需要找到最左边的，找不到输出-1。

查找函数实现

int find(int t) {      // 查找的目标数为t
    int l = 1, r = n;  // 初始化查找范围为[1, n]
    int ans = -1;      // 初始化ans为-1
    while (l <= r) {   // 搜索范围不为空，我们用闭区间来思考，l == r时，搜索范围还是有一个数的
        int mid = l + (r - l) / 2;   // 使用左端点+长度的一半计算中点。 因为(l + r) / 2中l + r可能会超过int范围。
        if (t == a[mid]) {           // 找到目标数。
            ans = mid;               // 更新答案。
            r = mid - 1;             // 因为左侧可能还有目标数t，还需要去左边继续查找。
        }
        if (t > a[mid]) l = mid + 1; // 目标数t大于中点数，去中点的右侧继续查找。改左指针。
        if (t < a[mid]) r = mid - 1; // 目标数t小于中点数，去中点的左侧继续查找。改右指针。
    }
    return ans;   // 若未找到，ans中就是初始值-1。
}

当数组中有重复数的时候，我们找到t时，更新答案，并且继续去左边找就好了。