Java二分法

二分查找题目

输入一个 n 个元素升序的整型数组 nums , 再输入一个目标值 target 。 编写一个方法: 使用二分法, 查找 nums 中的 target, 如果target存在, 则返回在数组中的下标, 否则返回 -1。

数组上任意一点的值:nums[i]

二分法查找流程

第一步

在数组中,取得中间下标。 中间下标=(最大下标-最小下标)/2+最小下标

第二步

判断中间下标的值和目标值target是否相等。

相等
直接返回中间下标
中间下标的值小于目标值target
缩小查找范围,将最小下标变为中间下标+1
中间下标的值大于目标值target
缩小查找范围,将最大的下标变为中间下标-1

代码示例

package com.binary;

public class Binary {
    //创建二分查找的方法,入参1:nums、入参2:target
    public int search(int[] nums,int target){
        int low=0;
        int high=nums.length-1;
        while(low<=high){
            int mid=(high-low)/2+low;
            int num=nums[mid];
            if(num==target){
                return mid;
            } else if(num>target){
                high=mid-1;
            } else {
                low=mid+1;
            }

        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums={1,2,3,4,5};
        int target=2;
        int result=new Binary().search(nums,target);
        System.out.println("应该输出的下标值为:1,实际输出的下标值为:"+result);
    }
}