河南广告制作公司网站_辽宁省建设工程信息网专家库怎么入_seo技术培训沈阳_企业门户网站

二分查找 - p1

• 时间复杂度：O(logN)
• 空间复杂度：O(1)

通过三个i, m, j下标，查找一个数组中的目标值target。想象其中i和j作为一个区间，m为i和j的中间值。数据通过与array[m]对比，不断缩短i, j这个区间，直到m指向target，到达查找的目的。中间值 = (i+j) / 2; 如果无法取得整数的中间数，则直接取结果的整数部分。

• 左侧下标 i
• 中间下标 m
• 右侧下标 j

i          m          j
|          |          |
V          V          V
1 2 4 8 16 32 64 128 512

算法条件规则

1. 当 i > j时，说明target并不在这个数组中。所以，target属于这个数组时: i <= j
2. 当 target > m 时，说明target一定在m的右侧（因为在数轴中右侧的数比m大）因此，我们要将j = m + 1。
3. 当 target < m 时，与上面同理，我们将j = m - 1

实现

int[] array = {1, 2, 4, 8, 16, 32, 64, 128, 512};

• 创建两个下标i, j

  int i = 0, j = array.length - 1;
  

  i为数组的起始位置，j为数组的下标总长度N-1

  i                     j
  |                     |
  v                     v
  1 2 4 8 16 32 64 128 512
  

• 编写条件规则1

  while (i <= j) { // 保证 i 不会大于 j...        
  }
  

• 计算中间值下标m

  int m = (i + j) / 2; // 计算中间下标
  

• 编写条件规则2-3

  if (array[m] > target) { // 中间值比目标值大j = m - 1;
  } else if (array[m] < target) { // 中间值比中间值小i = m + 1;
  } else { // 返回下标return m;
  }
  

这样我们就可以实现二分查找

文尾

• 完整代码：

  public class BinarySearchP1 {public static int achieve(int[] array, int target) {int i = 0, j = array.length - 1;while (i <= j) {int m = (i + j) / 2; // 计算中间下标// System.out.println("i = " + i + " m = " + m + " j = " + j);if (array[m] > target) { // 中间值比目标值大j = m - 1;} else if (array[m] < target) { // 中间值比中间值小i = m + 1;} else { // 返回下标return m;}}return -1;}public static void main(String[] args) {int[] array = {1, 2, 4, 8, 16, 32, 64, 128, 512};test(array);}public static void test(int[] array) {for (int cur: array) {int index = achieve(array, cur);System.out.println("expect = " + cur + "\n\toutput: " +"index = " + index + ", number = " + array[index]);}System.out.println("不存在的target测试。");for (int cur: array) {int target = cur + 100;int index = achieve(array, target);System.out.println("expect = -1" + "\n\toutput: " +"target: " + target + ", index = " + index);}}
  }
  

• 作者：PYmili

• 邮件：mc2005wj@163.com

• Q群：706128290