黑马程序员技术交流社区

标题: 【上海校区】二分查找 [打印本页]

---

作者: sjj632605    时间: 2019-2-26 20:37
标题: 【上海校区】二分查找

前言：首先第一要素需要明白,二分查找法适用于有序数组,记住,二分查找之前一定要排序!!!

二分查找元素代码:

[Java] 纯文本查看 复制代码

int base=0;

int top=size-1;

while(base<=top){

    mid=(top+base)/2;

        if(v[mid]==target) break; //mid为所求下标

        if(v[mid]<target) base=mid+1;

        if(v[mid]>target) top=mid-1;

}

二分查找过程: 我们可以把整个查找过程看成是不停地聚拢top和base,执行下面两种操作

[mw_shl_code=java,true]if(v[mid]<target) base=mid+1;

if(v[mid]>target) top=mid-1;

直到两者重合,然后越位退出循环,如果这个过程中出现了下面两个终止条件则提前结束:
1、v[mid]==target,即出现了查找目标,停止查找,返回mid为查到的目标下标. 最不理想的情况是直到最后top与base都会指向同一个元素target才返回.
2、如果数组中不存在targret,那么在最后一次循环体里面应该是这样的情形:top与base同时指向第一个大于target的元素,由于其大于target, 执行top=mid-1,那么结果就是base指向大于target的第一个数,top指向小3于target的最后一个数,然后退出循环.
利用二分查找定界

即给定一个有序数组,找到元素i,使得i之前的元素(包括i)都不大于target,i之后的元素都大于target.
可以分两种情况来考虑

1.数组中不存在target. 则根据第一部分的讨论,最后top和base同时指向第一个大于target的元素,然后进行最后一次小标变换,top=mid-1前移一个元素指向最后一个小于target的元素,base指向第一个大于target的元素.则top为所求

[Java] 纯文本查看 复制代码

while(base<=top){

    mid=(top+base)/2;

    if(v[mid]<target) base=mid+1;

    if(v[mid]>target) top=mid-1;

}

2.数组中存在target.我们只要把等于target的元素和小于target的元素归为一类,则最后结果仍然为top与base指向第一个大于target的元素,然后进行最后一次下标变换,top=mid-1前移一个元素,指向的是最后一个等于target的元素,base指向第一个大于target的元素.

[Java] 纯文本查看 复制代码

while(base<=top){

    mid=(top+base)/2;

    if(v[mid]<=target) base=mid+1;

    if(v[mid]>target) top=mid-1;

}

综合上面两种情况,最后的代码为

[Java] 纯文本查看 复制代码

while(base<=top){

    mid=(top+base)/2;

    if(v[mid]<=target) base=mid+1;

    if(v[mid]>target) top=mid-1;

}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2