您的位置:首页 > 房产 > 建筑 > 建筑公司网站常用长尾词_软件服务外包人才培养专业_百度电话人工服务_抖音seo排名

建筑公司网站常用长尾词_软件服务外包人才培养专业_百度电话人工服务_抖音seo排名

2024/12/23 16:48:52 来源:https://blog.csdn.net/qq_53280175/article/details/142368890  浏览:    关键词:建筑公司网站常用长尾词_软件服务外包人才培养专业_百度电话人工服务_抖音seo排名
建筑公司网站常用长尾词_软件服务外包人才培养专业_百度电话人工服务_抖音seo排名

二分查找 - p1

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

通过三个i, m, j下标,查找一个数组中的目标值target。想象其中ij作为一个区间,mij的中间值。数据通过与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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com