二分查找算法从有序数组中查找特定元素_利用二分法查找有序数组中某一元素

二分查找算法适用于有序数组（即从大到小或从小到大排序的数组），有序数组不一定是连续数组。
如果数组是有序的话，用二分查找法来寻找元素简单高效，用其他的方法基本上算炫技。

问题描述：查找一个元素（target）是否在有序数组(nums)中
一般解决方法：for循环比对，需要比对全数组
二分查找思想：比较target与数组中间值，如果target>中间值，则表示target在中间值的右边，令min=中间值下标，即舍去了中间值的左边数组。反之亦然，通过不断的取中间值来缩小查找范围，一次就缩小了1/2的范围,两次的话查找范围就变成了原数组长度1/4…

具体操作：
min=最小值下标;
max=最大值下标=数组nums.length-1;
中间值下标middle=(min+max)/2;
需要查找的元素为target;

while(min<=max) {
	middle=(min+max)/2;
	//目标值大于中间值，则令最小值下标=中间值下标，缩小了一半的查找空间
	if(target>nums[middle])min=middle;
	//目标值小于中间值，则令最大值下标=中间值下标
	if(target<nums[middle])max=middle;
				}
1
2
3
4
5
6
7

思想是这么个思想，但存在target不在数组中和可能会死循环。
需要改进一下：

public int rank(int[] nums,int target) {
		//二分查找
		int min=0,max=nums.length-1,middle;
		//target落在闭区间[min,max]中,通过与middle对比，缩小区间
while(min<=max) {
           //除法对middle向下取整
			middle=(max+min)/2;
			//target落在闭区间[middle+1,max]，所以更新min
			if(target>nums[middle])min=middle+1;
			//否则target落在闭区间[min,middle-1],更新max=middle-1
			else if(target<nums[middle])max=middle-1;
			else return middle;
		}
		return -1;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

如果不min=middle+1;和max=middle-1;则可能会发生target取数组最大值或最小值时无法取到就退出了循环
例如：
int[] nums=new int[] {1,4,7,9,28};
min=0,max=4,target=28；
middle=(0+4)/2=2 ,nums[middle]=7<target=28
min=middle=2,max=4
middle=(2+4)/2=3 ,nums[middle]=9<target=28
min=middle=3,max=4
middle=(3+4)/2=3,nums[middle]=9<target=28
min=middle=3,max=4
middle=(3+4)/2=3…永久循环
所以需要使用min=middle+1;和max=middle-1，让middle跳出除法的向下取整规则。