二分查找(对半搜索)

x33g5p2x  于12个月前 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(122)

二分查找(对半搜索)

本文采用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;
}

相关文章