二分查找算法详解 二分查找算法，是一种在有序数组中查找某一特定元素的搜索算法。 注意两点： (1)有序：查找之前元素必须是有序的，可以是数字值有序，也可以是字典序。为什么必须有序呢？ 如果部分有序或循环有序可以吗？ (2)数组：所有逻辑相邻的元素在物理存储上也是相邻的，确保可以随机存取。 算法思想： 搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大 于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一 半。 这里我们可以看到: (1) 如果查找值和中间值不相等的时候，我们可以确保可以下次的搜索范围可以缩小一半，正是由于所有元素都是有序的这一先决条件 (2) 我们每次查找的范围都是 理应包含 查找值的区间，当搜索停止时，如果仍未查找到，那么此时的搜索位置就应该是 查找值 应该处于的位置，只是该值不在数组中而已 算法实现及各种变形： 1. 非降序数组A, 查找 任一个 值==val 的元素，若找到则返回下标位置，若未找到则返回-1 2. 非降序数组A, 查找 第一个 值==val 的元素，若找到则返回下标位置，若未找到则返回-1 (类似：查找数组中元素最后一个 小于 val 值 的位置) 3. 非降序数组A, 查找 最后一个值==val 的元素，若找到则返回下标位置，若未找到则返回-1 (类似：查找数组中元素 第一个 大于 val 值 的位置) 4. 非降序数组A, 查找任一 值为 val 的元素，保证插入该元素后 数组仍然有序，返回可以插入的任一位置 5. 非降序数组A, 查找任一 值为 val 的元素，保证插入该元素后 数组仍然有序，返回可以插入的第一个位置 6. 非降序数组A, 查找任一 值为 val 的元素，保证插入该元素后 数组仍然有序，返回可以插入的最后一个位置 7. 非降序数组A, 查找 任一个 值==val 的元素，若找到则 返回一组下标区间(该区间所有值 ==val)，若未找到则返回-1 8. 非降序字符串数组A, 查找 任一个 值==val 的元素，若找到则返回下标位置，若未找到则返回-1(类似：未找到时返回应该插入点) 9. 循环有序数组中查找 == val 的元素，若找到则返回下标位置，若未找到则返回-1 1. 非降序数组A, 查找 任一个 值==val 的元素，若找到则返回下标位置，若未找到则返回-...
