摘自：https://blog.csdn.net/maoyuanming0806/article/details/78176957
二分查找是一种查询效率非常高的查找算法。又称折半查找。
起初在数据结构中学习递归时实现二分查找，实际上不用递归也可以实现，毕竟递归是需要开辟额外的空间的来辅助查询。本文就介绍两种方法
二分查找算法思想
有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。
一个情景：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
二分查找图示说明
二分查找优缺点
优点是比较次数少，查找速度快，平均性能好；
其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
使用条件：查找序列是顺序结构，有序。
一下为两种实现方法：
import java.util.Scanner;
public class Main{
// public static int [] a = new int[20];
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int a[] = {1,3,5,7,9,11,22};
int len = 5;
int w = erfen(a, 0, 5, 6);
int w2 = erfen2(a, 0, 5, 6);
System.out.println(w);
System.out.println(w2);
}
// 二分查找：递归版
public static int erfen(int[] a, int left, int right, int key) {
int mid = left + (right - left) / 2; // 这样可以避免 (left + right)益出现象
if(key < a[left] || key > a[right] || left > right){
return -1;
}
// System.out.println(a[mid]);
if(a[mid] == key) {
return mid;
}
else if(a[mid] > key){
return erfen(a, left, mid - 1, key);
}
else {
return erfen(a, mid + 1, right, key);
}
}
// 用循环做二分查找
public static int erfen2(int[] a, int left, int right, int key) {
int mid;
while(left <= right) {
mid = left + (right - left) / 2;
if(key == a[mid]) {
return mid;
}
else if(key < a[mid]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
}
/*
*/
原文：https://www.cnblogs.com/zhumengdexiaobai/p/10503838.html