二分查找（对半搜索）

本文采用Java书写选择排序，其他语言类似可以借鉴着写

所谓二分查找和对半搜索，即对于升序（或者降序）的有序序列进行查找时，由于有序我们可以直接从中间查找相等返回。大于则在右侧子序列中进行二分查找，小于则对左侧子序列进行二分查找。直至找到或者子序列只有一个元素为止。

代码实现

• 迭代方法实现

public int binSearch(int[] nums, int target) {
    int index, low = 0, hight=nums.length-1;
    while (low<=hight)
    {
        index = (low+hight) / 2;
        if(target<nums[index]) hight = index - 1;
        else if(target>nums[index]) low = index + 1;
        else return index;
    }
    return -1;
}

• 递归方法实现

public int binSearch(int[] nums, int target) {
return binSearch(nums,target,0,nums.length-1);
}
public int binSearch(int[] nums, int target, int low, int high){
    int index = -1;
    if(low<=high){
        index = (low+high)/2;
        if(target<nums[index])
            return binSearch(nums,target,low,index-1);
        else if(target>nums[index])
            return binSearch(nums,target,index+1,high);
        else return index;
    }
    return index;
}