一. 二分法

问题分支:

1. 在一个有序数组中,找某一个数是否存在
2. 在一个有序数组中,找>=某个数最左侧的位置
3. 在一个有序数组中,找<=某个数最右侧的位置
4. 局部最小值问题

写在前面的话：

写对「二分查找」的重点，从来不在于「二分查找」我们用的是哪一个模板（所有的模板背后的逻辑都一样），更不在于我们设置的区间是「左闭右闭」还是「左开右闭」。而在于 认真看题、仔细分析题意，根据题目的条件和要求思考如何缩减区间，清楚地知道每一轮在什么样的情况下，搜索的范围是什么，进而设置左右边界。

我们需要分析清楚题目的意思，分析清楚要找的答案需要满足什么性质。应该清楚模板具体的用法，明白需要根据题意灵活处理、需要变通的地方，不可以认为每一行代码都是模板规定死的写法，不可以盲目套用、死记硬背。

二分查找只有一个思想，那就是：逐步缩小搜索区间。

本题解向大家介绍的，使用 left 和 right 向中间靠拢的方法，有一个非常强的语义，那就是：当 left 与 right 重合的时候，我们就找到了问题的答案，使用这种写法有一个巨大的好处，那就是返回值不需要考虑返回 left 还是 right，因为退出循环以后，它们是重合的。

在做题的过程中，会遇到两个难点：

1. 取 mid 的时候，有些时候需要 +1，这是因为需要避免死循环；
2. 只把区间分成两个部分，这是因为：只有这样，退出循环的时候才有 left 与 right 重合，我们才敢说，找到了问题的答案。（这两个难点，在练习的过程中，会逐渐清晰，不用着急一下子搞懂，事实上并不难理解）。

两个栗子:

第一种:

     //二分查找
for (int i = 0; i < n; i++) {   //要找到小于等于当前query的最大价格
    int left = 0, right = m - 1;
    while (left < right) {  //当left=right的时候相当于已经找到了小于等于当前query的最大值，不需要再进去，这和要找到某个相等的值有所不同
        //int mid = left + (right - left) / 2;
        int mid = left + (right - left) / 2 + 1;  //这个一定要加1，没太理解
        if (items[mid][0] > queries[i]) {   //当此时mid比当前query大时，肯定不满足条件，可以跳过
            right = mid - 1;
        } else {    //小于等于时，可能满足条件，需要保留
            left = mid;
        }
    }
    ans[i] = items[left][0] <= queries[i] ? items[left][1] : 0;
}

第二种:

//这一种也能过，二分杀我，太多的细节了
for (int i = 0; i < n; i++) {   //要找到小于等于当前query的最大价格
    int left = 0, right = m - 1;
    while (left <= right) {  
        int mid = left + (right - left) / 2;
        //int mid = left + (right - left) / 2 + 1;  //这个一定要加1，没太理解
        if (items[mid][0] > queries[i]) {  
            right = mid - 1;
        } else {   
            left = mid + 1;
            ans[i] = items[mid][1];
        }
    }
    //ans[i] = items[left][0] <= queries[i] ? items[left][1] : 0;
}

回答 1：取 mid 为什么要加 1
int mid = left + (right - left) / 2 + 1; （+1 也可以写在括号里面，目的是为了改变整数除法默认下取整的行为）只出现在 while (left < right) 这种写法里，因为这种写法要求我们一定要弄清楚 mid 位置的值是保留还是剔除：

• 如果保留，就不加 1 或者减 1；
• 如果剔除，就要加 1 或者减 1。

需要重点理解： if 和 else 里面出现了 left = mid ，加 1 是避免出现死循环。你可以试试看取 mid 的时候不加 1 ，一定会有某一些测试用例 超时。

原因：整数除法是下取整。取 mid 的时候 不能做到真正取到中间位置，例如 left = 3, right = 4， mid = (left + right) / 2 = 3；

你给的「第一种」代码里 if 和 else 里面的代码表示：根据 mid 位置的值把区间 [left..right] 分成两个部分：[left..mid - 1] 与 [mid..right]。left = mid 一定需要与 right = mid - 1 配对使用。因为：

left = mid 表示下一轮搜索区间是 [mid..right] ，所以设置 left = mid；
right = mid - 1 表示下一轮搜索区间是区间 [left..mid - 1]，所以设置 right = mid - 1。
当区间里只剩下两个元素的时候 left 的值等于 mid 的值，还看上面的例子 left = 3, right = 4， mid = (left + right) / 2 = 3 = mid，此时一旦进入这个区间 [mid..right] ，代码执行 left = mid ，搜索区间不能缩小，所以进入死循环。

如果实在对着屏幕很难理解为什么会出现死循环，在循环体里把 left 和 right 的值打印出来看一下就清楚了。「力扣」第 69 题是这种情况下最容易看到死循环的问题，我写过题解展示过这种死循环，可以看 这里，可以直接翻到最后「问答」那里，看第 3 点。

回答 2：你给出的 「第二种」 代码为什么也能通过
你给出的 「第二种」 代码：while (left <= right) 这种写法，这种写法要求：if 和 else 里面的 right 和 left 都要 -1 或者 + 1，它没有死循环的问题，但是有一点要注意的是：一定要在 mid 位置的值可能是解的时候，把结果保存下来，也就是代码中 ans[i] = items[mid]; 的意思。

本题 ans[i] = items[mid]; 就设置在 else 里，表示当 items[mid] <= queries[i] 的时候，mid 位置的值有可能是我们要找的（至于为什么是这样，看题目）。当 left == right 的时候，循环体还会继续执行，由于 left 和 right 一定会 +1 或者 -1，还会继续查找，所以没有死循环的问题，由于之前保留过 ans 的值，所以不会丢失解。

我帮你简单总结一下网络上常见的三种模板的区别：

总结：三种模板写法比较

• 模板一：while (left <= right) ，这种写法里面的 left 和 right 都要加 1 或者减 1，还要判断 mid 位置的值有可能是解的时候，把 mid 的值保存下来，所以这种写法别人也叫带 ans 的写法，我以前看到力扣的大佬零神就比较喜欢这样写；

• 模板二：while (left < right) 这种写法需要清楚 mid 位置的值是否保留，所以一定是 left = mid 与 right = mid - 1 配对，left = mid + 1 与 right = mid 配对。这种模板最难理解的地方就是出现 left = mid 的时候，一定要把取 mid 的表达式 +1。好处是退出循环以后，很多时候 left 与 right 就是要找的解，而且这种写法也要求我们必须弄清楚 mid 到底有没有可能是解；

  这里有个小技巧，一般我会在注释里写上「下一轮搜索区间是什么」。如果下一轮搜索区间是 [mid..right] ，这个时候就设置 left = mid，这种情况的反面区间就是 [left..mid - 1] ，那么 else 就设置 right = mid - 1，所以就不用记忆配对关系了。

• 模板三：while (left + 1 < right) 这种写法里面的 left 和 right 都不加 1 或者减 1，意思就是都认为 mid 可能是要找的值，所以退出循环以后一定要再判断一下 left 和 right 哪个有可能是解。退出 while (left + 1 < right) 循环以后，区间里剩下两个元素，所以还要单独判断一下这两个位置哪个是要找的元素的值，很多时候会增加不必要的判断逻辑。

三种模板实际上都是一个意思：

• 模板二说一定要搞清楚 mid 位置是不是要保留，退出循环以后 left 与 right 重合，区间 [left..right] 只有 1 个元素；
• 模板三说 mid 全部保留，退出循环以后 left 在左，right 在右，区间 [left..right] 有 2 个元素；
• 模板一说 mid 全部不保留，退出循环以后 left 在右，right 在左，区间 [left..right] 为空区间。
• 模板一和模板三屏蔽了 + 1 还是 -1 的细节，但是都有相应的「补救措施」。

不管哪种模板一定要判断的是 下一轮「向左找」还是「向右找」，还有 mid 是不是有可能是问题的答案，这一点应该从题目中分析得到，所以一定要认真审题哦。

1. 在一个有序数组中,找某一个数是否存在

思路:

1. 找到arr[]的一个中点:
2. 如果中点比n小,那么中点左面的数全部舍弃.
3. 如果中点比n大,那么中点右面的数全部舍弃
4. 得到舍弃后的数组
5. 再找中点….

public static boolean exist(int[] sortedArr, int num) {
        if (sortedArr == null || sortedArr.length == 0) {
            return false;
        }
        int L = 0;
        int R = sortedArr.length - 1;
        int mid = 0;
        // L..R
        while (L < R) { // L..R 至少两个数的时候
            mid = L + ((R - L) >> 1);
            if (sortedArr[mid] == num) {
                return true;
            } else if (sortedArr[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return sortedArr[L] == num;
    }

2. 在一个有序数组中,找>=某个数最左侧的位置

例:  arr[ 1 , 1 , 2 , 2 , 2 , 2 , 3 , 3 , 3 , 4 , 5 , 5 , 5 , 6 , 6 , 6 , 7 , 8 , 8] 
    索引  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18
    num = 2
        return 3
    num = 3
        return 6

思路: num = 2

1. 先找到中点 arr[9] 为 4 大于 num  , arr[9] 右侧舍去
2. 再找中点 arr[4] 为 2 等于 num , t = 4
3. 再找中点 arr[2] 为 2 等于 num , 更新 t = 2
4. 再找中点 arr [1] 为 1 小于 num , arr[1] 左侧舍去
5. 发现 arr[1] 和 arr[2] 中间没有数字 ,返回最后得到的那个 t

从右向左筛选 所以 ans = mid 放在右面的if里

代码:

// 在arr上，找满足>=value的最左位置
    public static int nearestIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1; // 记录最左的对号
        while (L <= R) { // 至少一个数的时候
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }

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

3. 在一个有序数组中,找<=某个数最右侧的位置

public static int nearestIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1; // 记录最右的对号
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] <= value) {
                index = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return index;
    }

public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len;
        // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }
        return left;
    }
}

4. 局部最小值问题

无序 相邻不相等 数组 arr[0~n-1] 找局部最小

1. 如果arr只有一个数则直接返回
2. 当在最左侧的时候: [0] < [1] 0位置是局部最小
3. 当在最右侧的时候: [n-2] < [n-1] n-2位置是局部最小
4. 当在中间的时候: 左 < [i] > 右

只需要返回一个局部最小值

代码 :越界

public class Code04_BSAwesome {

    //arr 整体无序
    //arr 相邻的数不相等!
    public static int oneMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int N = arr.length;
        if (N == 1) {
            return 0;
        }
//        if(N == 2){
//            return arr[0] <arr[1] ? 0 : 1;
//        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[N - 1] < arr[N - 2]) {
            return N - 1;
        }
        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        // L <= R越界
        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid + 1] > arr[mid]) {
                ans =  mid;
                break;
            } else {
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
        }
        return  ans;
    }

代码:改正

// arr 相邻的数不相等！
public static int oneMinIndex(int[] arr) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int N = arr.length;
    if (N == 1) {
        return 0;
    }
    if (arr[0] < arr[1]) {
        return 0;
    }
    if (arr[N - 1] < arr[N - 2]) {
        return N - 1;
    }
    int L = 0;
    int R = N - 1;
    // L...R 肯定有局部最小
    while (L < R - 1) {
        int mid = (L + R) / 2;
        if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
            return mid;
        } else {
            if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
    }
    return arr[L] < arr[R] ? L : R;
}

防止 类似[3,2,3,2,3] 越界 我们将while(L<=R) 改成 while( L < R - 1 ) 从while出来时最后剩下两个数,可以防止越界

测试代码

 // 生成随机数组，且相邻数不相等
    public static int[] randomArray(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen);
        int[] arr = new int[len];
        if (len > 0) {
            arr[0] = (int) (Math.random() * maxValue);
            for (int i = 1; i < len; i++) {
                do {
                    arr[i] = (int) (Math.random() * maxValue);
                } while (arr[i] == arr[i - 1]);
            }
        }
        return arr;
    }

    // 也用于测试
    public static boolean check(int[] arr, int minIndex) {
        if (arr.length == 0) {
            return minIndex == -1;
        }
        int left = minIndex - 1;
        int right = minIndex + 1;
        boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
        boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
        return leftBigger && rightBigger;
    }

    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxLen = 100;
        int maxValue = 200;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int ans = oneMinIndex(arr);
            if (!check(arr, ans)) {
                printArray(arr);
                System.out.println(ans);
                break;
            }
        }
        System.out.println("测试结束");
    }

5. 题目

题型一：二分求下标（在数组中查找符合条件的元素的下标）

说明：

• 第 704 题：二分查找的最原始问题，使用两边夹的二分查找方法需要后处理（退出循环以后，还需要判断 left 或 right 位置的值是不是问题的答案）；
• 第 34 题、第 35 题：需要明白这一类问题的共同特点，请见 这里；
• 第 300 题：特别经典的一道「动态规划」，二分查找的思路基于「动态规划」的状态定义得到，代码很像第 35 题；
• 第 658 题：这个问题二分的写法需要做复杂的分类讨论，可以放在以后做；
• 第 4 题：二分查找里最难的问题，重点在于理解：① 为什么是在短数组里找边界；② 深刻理解搜索边界的意义。 | 题号 | 链接 | 题解 | | —- | —- | —- | | 704 | 二分查找（简单） | | | 35 | 搜索插入位置（简单） | 【视频讲解】、文字题解 | | 300 | 最长上升子序列（中等） | 文字题解 | | 34 | 在排序数组中查找元素的第一个和最后一个位置（简单） | 【视频讲解】、文字题解 | | 611 | 有效三角形的个数 | 文字题解 | | 658 | 找到 K 个最接近的元素（中等） | 文字题解 | | 436 | 寻找右区间（中等） | 文字题解 | | 1237 | 找出给定方程的正整数解（中等） | | | 1300 | 转变数组后最接近目标值的数组和（中等） | 文字题解 | | 4 | 寻找两个有序数组的中位数（困难） | 【视频讲解】、文字题解 |

使用二分查找的前提不一定非要是「有序数组」。旋转有序数组（下表前 4 题）、山脉数组（下表后 2 题）里的查找问题也可以使用「二分查找」。这些问题的解决思路是：利用 局部单调性，逐步缩小搜索区间。

704. 二分查找

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

35. 搜索插入位置

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

题意分析
根据示例，分析题目要我们返回的「插入元素的位置」是什么。

根据「示例 3」：


输入: [1, 3, 5, 6], 7
输出: 4

我们知道：如果目标元素 严格大于 输入数组中的最后一个元素，题目需要我们返回数组的最后一个元素的下标 +1（也就是数组的长度）。

又根据「示例 2」：


输入: [1, 3, 5, 6], 2
输出: 1

我们知道：题目要我们返回第 11 个 大于等于 目标元素 2 的下标（分析出这一点非常重要），因此返回 1。等于的情况可以看「示例 1」。

思路分析
在有序数组中查找，可以使用「二分查找」。

根据「题意分析」中对示例的描述：

情况 1：如果当前 mid 看到的数值严格小于 target，那么 mid 以及 mid 左边的所有元素就一定不是「插入元素的位置」，因此下一轮搜索区间是 [mid + 1..right]，下一轮把 left 移动到 mid + 1 位置，因此设置 left = mid + 1；

情况 2：否则，如果 mid 看到的数值大于等于 target，那么 mid 可能是「插入元素的位置」，mid 的右边一定不存在「插入元素的位置」。如果 mid 的左边不存在「插入元素的位置」，我们才可以说 mid 是「插入元素的位置」。因此下一轮搜索区间是 [left..mid]，下一轮把 right 移动到 mid 位置，因此设置 right = mid。
说明：上面的两点中，「情况 2」其实不用分析得那么细致， 因为只要「情况 1」的区间分析是正确的，「情况 2」一定是「情况 1」得到的区间的反面区间。

参考代码 1：

public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        // 特殊判断
        if (nums[len - 1] < target) {
            return len;
        }

        // 程序走到这里一定有 nums[len - 1] >= target，插入位置在区间 [0..len - 1]
        int left = 0;
        int right = len - 1;
        // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }
        return left;
    }
}

说明：while (left < right) 表示当 left 与 right 重合的时候，搜索终止。根据题意和示例，区间 nums[left..right] 里一定存在「插入元素的位置」，且 while 循环里只把区间分成两个部分，退出循环的时候一定有 left == right 成立，因此返回 left 或者 right 都可以。

复杂度分析：

时间复杂度：O(log N)，这里 NN 是输入数组的长度；
空间复杂度：O(1)。
既然 len 也有可能是答案，可以在初始化的时候，把 right 设置成 len，在一开始的时候就不需要特殊判断了。

参考代码 2：

public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len;
        // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }
        return left;
    }
}

复杂度分析：（同参考代码 1）

题型二：二分答案（在一个有范围的区间里搜索一个整数）

如果题目要我们找一个整数，这个整数有确定的范围，可以通过二分查找逐渐缩小范围，最后逼近到一个数。

定位一个有范围的整数，这件事情也叫「二分答案」或者叫「二分结果」。如果题目要求的是一个整数，这个整数有明确的范围，可以考虑使用二分查找。

事实上，二分答案是我们最早接触的二分查找的场景。「幸运 52」里猜价格游戏，就是「二分查找」算法的典型应用：先随便猜一个数，如果猜中，游戏结束。如果猜大了，往小猜；如果猜小了，往大猜。

说明：

• 第 69 题：在一个整数范围里查找一个整数，也是二分查找法的应用场景；
• 第 275 题：这个问题题解题意得花很多时间，可以跳过不做；
• 第 278 题：在一个整数范围里查找一个整数，不是在输入数组里使用二分查找。这个问题二分查找的解法很反常规（不应该用时间换空间），知道即可。 | 题号 | 链接 | 题解 | | —- | —- | —- | | 69 | x 的平方根（简单） | 文字题解 | | 287 | 寻找重复数（中等） | 文字题解 | | 374 | 猜数字大小（简单） | 文字题解 | | 275 | H指数 II（中等） | 文字题解 | | 1283 | 使结果不超过阈值的最小除数（中等） | 文字题解 | | 1292 | 元素和小于等于阈值的正方形的最大边长（中等） | |

题型三：二分答案的升级版（每一次缩小区间的时候都需要遍历数组）

说明：这一类问题本质上还是「题型二」（二分答案），但是初学的时候会觉得有一些绕。这一类问题的问法都差不多，关键字是「连续」、「正整数」，请大家注意捕捉题目中这样的关键信息。

这里给出的问题解法都一样，会一题等于会其它题。问题的场景会告诉我们：目标变量和另一个变量有相关关系（一般是线性关系），目标变量的性质不好推测，但是另一个变量的性质相对容易推测（满足某种意义上的单调性）。这样的问题的判别函数通常会写成一个函数的形式。

这一类问题可以统称为「 最大值极小化 」问题，最原始的问题场景是木棍切割问题，这道题的原始问题是「力扣」第 410 题（分割数组的最大值（困难））。

思路是这样的：

• 分析出题目要我们找一个整数，这个整数有范围，所以可以用二分查找；
• 分析出 单调性，一般来说是一个变量 a 的值大了，另一个变量 b 的值就变小，而「另一个变量的值」 b 有限制，因此可以通过调整 a 的值达到控制 b 的效果；
• 这一类问题的题目条件一定会给出 连续、正整数 这样的关键字。如果没有，问题场景也一定蕴含了这两个关键信息。

参考资料：

• 二分查找之「最大值极小化」相关问题及解题步骤
• 二分查找之「最大值极小化」例题选讲

以下给出的问题无一例外。

补充：「力扣」第 209 题：长度最小的子数组（中等），这道题可以使用「前缀和 + 二分查找」或者「滑动窗口」来做，一定要想清楚，为什么可以使用这些方法。

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int first = firstfind(nums,target);
        if(first == -1){
            return new int[]{-1,-1};
        }
        int last = lastfind(nums,target);
        return new int[]{first,last};
    }

    public int firstfind(int[] nums ,int target){
        int right = nums.length - 1;
        int left = 0;
        while(left < right){
            int mid = left + ((right - left)>>1);
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }

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

}

400. 第 N 位数字

首先分析

1. 确定n对应的数字是几位数字
2. 计算具体是哪一个数字

我们知道 0-9 是一位数， 一位数共有9个， 总计产生 9 1 = 9 位数字
我们知道 10-99 是两位数， 一位数共有90个， 总计产生 90 2 = 180 位数字
…

方法、找规律
今天这道题我们暴力求解也是可以的，但是 n 的范围太大，可能会超时，所以，我们另辟蹊径。

我们先来看看整数有哪些规律：

一位数总共有 9 个整数，共 9 个数字；
两位数总共有 90 个整数，共 90 2 个数字；
三位数总共有 900 个整数，共 900 3 个数字；
所以，我们可以先简单得求出来 n 应该是在哪个位数的整数中。

假设，我们算出来 n 在三位数中，这时候 n 还剩下 20，那么，接下来我们可以确定 n 是在具体哪个整数中。

我们拿 20/3=6 ，说明 n 在 100+6=106 这个整数中，但是，为了防止边界情况，我们使用 (20-1)/3，具体你可以想像不是20而是21，是不是在107这个整数中呢？你可以自己算一下。

确定到具体哪个整数了，那就很容易确定是在这个整数的哪个位了。

具体的做法是拿 20−6∗3=2，说明在 106 的第2位，也就是数字 0。

好了，具体的我们来看代码，代码中也加入了很多注释，如果你还是不太理解，可以在 IDEA 中打个断点调试一下，相信你会更清楚：

二. 插值查找

二分法改进(适用于比较平均的关键字分布)

public static boolean exist(int[] sortedArr, int num) {
        if (sortedArr == null || sortedArr.length == 0) {
            return false;
        }
        int L = 0;
        int R = sortedArr.length - 1;
        int mid = 0;
        // L..R
        while (L < R) { // L..R 至少两个数的时候
            mid = L + (R - L) * (key - sortedArr[L])/(sortedArr[R] - sortedArr[L]);
            if (sortedArr[mid] == num) {
                return true;
            } else if (sortedArr[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return sortedArr[L] == num;
    }

%20*%20(key%20-%20sortedArr%5BL%5D)%2F(sortedArr%5BR%5D%20-%20sortedArr%5BL%5D)%3B%0A#card=math&code=mid%20%3D%20L%20%2B%20%28R%20-%20L%29%20%2A%20%28key%20-%20sortedArr%5BL%5D%29%2F%28sortedArr%5BR%5D%20-%20sortedArr%5BL%5D%29%3B%0A)

三. 斐波那契查找

public class FibonacciSearch {

    /**
     * @param args
     */
    public final static int MAXSIZE = 20;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] f = fibonacci();
        for (int i : f) {
            System.out.print(i + " ");
        }
        System.out.println();

        int[] data = { 1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88 };

        int search = 39;
        int position = fibonacciSearch(data, search);
        System.out.println("值" + search + "的元素位置为：" + position);
    }

    /**
     * 斐波那契数列
     * 
     * @return
     */
    public static int[] fibonacci() {
        int[] f = new int[20];
        int i = 0;
        f[0] = 1;
        f[1] = 1;
        for (i = 2; i < MAXSIZE; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    public static int fibonacciSearch(int[] data, int key) {
        int low = 0;
        int high = data.length - 1;
        int mid = 0;

        // 斐波那契分割数值下标
        int k = 0;

        // 序列元素个数
        int i = 0;

        // 获取斐波那契数列
        int[] f = fibonacci();

        // 获取斐波那契分割数值下标
        while (data.length > f[k] - 1) {
            k++;
        }

        // 创建临时数组
        int[] temp = new int[f[k] - 1];
        for (int j = 0; j < data.lengt敏感词emp[j] = data[j];
        }

        // 序列补充至f[k]个元素
        // 补充的元素值为最后一个元素的值
        for (i = data.length; i < f[k] - 1; i++) {
            temp[i] = temp[high];
        }

        for (int j : temp) {
            System.out.print(j + " ");
        }
        System.out.println();

        while (low <= high) {
            // low：起始位置
            // 前半部分有f[k-1]个元素，由于下标从0开始
            // 则-1 获取 黄金分割位置元素的下标
            mid = low + f[k - 1] - 1;

            if (temp[mid] > key) {
                // 查找前半部分，高位指针移动
                high = mid - 1;
                // （全部元素） = （前半部分）+（后半部分）
                // f[k] = f[k-1] + f[k-1]
                // 因为前半部分有f[k-1]个元素，所以 k = k-1
                k = k - 1;
            } else if (temp[mid] < key) {
                // 查找后半部分，高位指针移动
                low = mid + 1;
                // （全部元素） = （前半部分）+（后半部分）
                // f[k] = f[k-1] + f[k-1]
                // 因为后半部分有f[k-1]个元素，所以 k = k-2
                k = k - 2;
            } else {
                // 如果为真则找到相应的位置
                if (mid <= high) {
                    return mid;
                } else {
                    // 出现这种情况是查找到补充的元素
                    // 而补充的元素与high位置的元素一样
                    return high;
                }
            }
        }
        return -1;
    }
}