二分查找也叫折半查找，是一种基本的查找算法，这种查找方法需要待查的表满足两个条件

首先，查找表必须使用顺序的存储结构

其次，查找表必须按关键字大小有序排列

 

算法的基本思想是：

将查找表中间位置数据元素的关键字与给定关键字比较，如果相等则查找成功；

否则利用中间元素将表一分为二，如果中间关键字大于给定关键字，则在前一子表中进行折半查找，否则在后一子表中进行折半查找。重复以上过程直到找到满足条件的元素，则查找成功；

或知道子表为空为止，此时查找不成功。

 

二分查找的非递归写法：

 1 public int firstOccurrence(int [] nums,int target){
 2         int low = 0,high = nums.length - 1;
 3         while(low <=  high){
 4             int mid = low + (high-low)/2;
 5             if(nums[mid] == target){
 6                 return mid;
 7             }
 8             if(nums[mid] < target){
 9                 low = mid+1;
10             }else {
11                 high = mid-1;
12             }
13         }
14         return -1;
15     }

版权声明：本文为stevewys原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/stevewys/p/11077302.html