二分查找的思路比较简单,步骤如下:
选择一个标志 i 将集合 L 分为二个子集合,一般可以使用中位数;
判断标志 L(i) 是否能与要查找的值 des 相等,相等则直接返回结果;
如果不相等,需要判断...二分查找的最差情况是,不断查找到最后 1 个数字才完成判断,那么此时需要的最大的复杂度就是 O(logn)。...在数组 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } 中,查找 8 是否出现过
首先判断 8 和中位数 5 的大小关系。...因为 8 更大,所以在更小的范围 6, 7, 8, 9, 10 中继续查找。此时更小的范围的中位数是 8。由于 8 等于中位数 8,所以查找到并打印查找到的 8 对应在数组中的 index 值。...在面对陌生问题时,需要注意原问题的数据是否有序,预期的时间复杂度是否带有 logn 项,是否可以通过小问题的答案合并出原问题的答案。如果这些先决条件都满足,就应该第一时间想到分治法。