- it技术
- 十六、程序员10大算法之二分查找算法（非递归）
一、二分查找算法介绍
二、代码实现
package binarysearchnorecursion
;
public class BinarySearchNoRecur {
public static void main(String
[] args
) {
int[] arr
= {1,3,8,10,11,67,100};
int index1
= binarySearch(arr
,100);
System
.out
.println("index1=" + index1
);
int index2
= binarySearchRur(arr
,0,arr
.length
,100);
System
.out
.println("index2=" + index2
);
}
public static int binarySearch(int[] arr
,int target
){
int left
= 0;
int right
= arr
.length
-1;
while(left
<= right
){
int mid
= (right
- left
) / 2 + left
;
if(arr
[mid
] == target
){
return mid
;
}else if(arr
[mid
] > target
){
right
= mid
- 1;
}else{
left
= mid
+ 1;
}
}
return -1;
}
public static int binarySearchRur(int[] arr
,int left
,int right
,int target
){
int mid
=(right
- left
) / 2 + left
;
if(arr
[mid
] == target
){
return mid
;
}
if(left
>= right
){
return -1;
}
else if(arr
[mid
] > target
){
return binarySearchRur(arr
,left
,mid
-1,target
);
}else if(arr
[mid
] < target
){
return binarySearchRur(arr
,mid
+ 1,right
,target
);
}
return -1;
}
}
三、测试结果
index1
=6
index2
=6
