Java教程

二分搜索

本文主要是介绍二分搜索,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二分搜索

应用:

应用查找顺序数据结构的目标值,如有序数组等。

原理:

  1. 检索出数组索引的第一个和最后一个(left与right)
  2. 得到mid,为left与right的一半
    • mid=(left+right)/2
    • mid=left+(right-left)/2,建议使用这个,当left与right过大时,相加第一个会溢出
  3. 接下来用while循环(循环的条件是left<=right)找到目标值(假设数组从小到大排序),while循环中的条件是”>=“,跳出循环后left==right+1
    • 如果target大于nums[mid],则说明target在mid右边,令left=mid+1
    • 如果target小于nums[mid],则说明target在mid左边,令right=mid-1
    • 如果target等于nums[mid],则说明target就在mid,返回mid
  4. 最后返回left,即得到的数组元素的位置

代码实现:

class Solution{
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            //mid的取值
            int mid=left+(right-left)/2;
            if(nums[mid]>target)right=mid-1;
            else if(nums[mid]<target)left=mid+1;
            else return mid;
        }
        return left;
    }
}

image

这篇关于二分搜索的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!