二分查找算法详解.docx

二分查找算法详解
二分查找算法，是一种在有序数组中查找某一特定元素的搜索算法。注意两点：
有序：查找之前元素必须是有序的，可以是数字值有序，也可以是字典序。为什么必须有序呢？如果部分有序或循环有序可以吗？
数组：所有逻辑相邻的元素在物mid;
{
3
4
5
6
7
8
9
10
11
12
13
14
if(mid>0&&a[mid-1]!=val)returnmid;
high=mid-1;
}
}
return-1;
}
非降序数组A,查找最后一个值==val的元素，若找到则返回下标位置，若未找到则返回-1(类似：查找数组中元素第一个大于val值的位置)
算法思想与第2题相同
intsearch_last(int*a,intlen,intval)
{
assert(a!=NULL&&len>1);
intlow=0;
inthigh=len-1;
while(low<=high){
intmid=low+(high-low)/2;
if(val<a[mid]){
high=mid-1;
}elseif(val>a[mid]){
low=mid+1;
}else{
if(mid==(len-1))returnmid;
if(mid<(len-1)&&a[mid+1]!=val)returnmid;
low=mid+1;
}
}
return-1;
}
非降序数组A,查找任一值为val的元素，保证插入该元素后数组仍然有序，返回可以插入的任一位置
当a[mid]==val则返回mid,因为在该位置插入val数组一定保证有序
当循环结束后仍未查找到val值，我们之前说过，此时一定有high=low+1,其实查找值永远都应该在low和high组成的区间内，现在区间内没空位了，所以可以宣告该值没有查找到，
如果仍然有空位，则val一定在该区间内。也就是说此时的low和high这两个值就是val应该处于的位置，因为通常都是在位置之前插入，所以此时直接返回low即可
intinsert(int*a,intlen,intval)
{
assert(a!=NULL&&len>0);
intlow=0;
inthigh=len-1;
while(low<=high){
intmid=low+(high-low)/2;
if(val<a[mid]){
high=mid-1;
}elseif(val>a[mid]){
low=mid+1;
}else{
returnmid;
}
}
returnlow;
}
非降序数组A,查找任一值为val的元素，保证插入该元素后数组仍然有序，返回可以插入的第一个位置
因为是要求第一个可以插入的位置，当查找值不在数组中时，插入的位置是唯一的，即returnlow
当查找值出现在数组中时，此时就演变成了查找第一个==val的值，详见第2题
intinsert_first(int*a,intlen,intval)
2{
3
assert(a!=NULL&&len>1);
4
intlow=0;
5
inthigh=len-1;
6
while(low<=high){
7
intmid=