Data7.26二分查找

问题描述

• 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜
  索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

• 输入: nums = [-1,0,3,5,9,12], target = 9
• 输出: 4
• 解释: 9 出现在 nums 中并且下标为 4

示例 2:

• 输入: nums = [-1,0,3,5,9,12], target = 2
• 输出: -1
• 解释: 2 不存在 nums 中因此返回 -1

提示：

• 你可以假设 nums 中的所有元素是不重复的。
• n 将在 [1, 10000]之间。
• nums 的每个元素都将在 [-9999, 9999]之间

涉及的知识点

• 二分查找：也称折半査找，其优点是查找速度快，缺点是要求所要査找的数据必须是有序序列。
  • 该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较，如果相等，则表示査找成功，否则将以该位置为基准将所要査找的序列分为左右两部分。
  • 接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系，来选择所要査找元素可能存在的那部分序列，对其采用同样的方法进行査找，直至能够确定所要查找的元素是否存在。

思路

• 根据输入的数组然后去判断数组是否是升序序列，是就继续执行；
• target与数列中间值来比较，当中间值大时，往子区间[left,mid-1]查找；当中间值小时，往子区间[mid+1,right]查找；当中间值等于目标数值时输出下标；
• 当在子区间[left,mid-1]或子区间[mid+1,right]或中间区间查找不到时，则输出-1；

代码

package data;
import java.util.Scanner;
public class Data726 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n,target,i;
        n = cin.nextInt();
        System.out.print("nums=");
        int nums[] = new int[n];
        for(i = 0; i < n; i++)
        {
            nums[i] = cin.nextInt();
        }
        if(judge(nums,n))
        {
            System.out.print("target=");
            target = cin.nextInt();
            if(binarySearch(nums,0,n-1,target) != -1)
            {
                System.out.println(binarySearch(nums,0,n-1,target));
            }
            else
            {
                System.out.println("-1");
            }
        }
        else
                System.out.println("-1");
    }

    public static boolean judge(int[] x, int num) {
        int minx = x[0];
        boolean flag = true;//标志是否是升序数组；
        for (int j = 1; j < num; j++) {
            if (x[j] < minx) {
                flag = flag;
                break;
            } 

else {
minx = x[j];
}
}
if (flag == false)
return false;
else
return true;
}

public static int binarySearch(int A[], int left, int right, int x) {
    int mid; //mid为left和right的中间点
    while (left <= right) {
        mid = (left + right) / 2;//mid= 0+4（5-1）/2=2
        if (A[mid] == x) {//nums[2] = 3!= target=5
            return mid + 1;//找到x，返回下标
        }
        else if (A[mid] > x) //中间数大于x  --A[2] = 3 > 2
        {
            right = mid - 1; //往子区间[left,mid-1]查找--right = 2 -1
        }
        else//中间数小于x---3<5
        {
            left = mid + 1; //往子区间[mid+1,right]查找--left= 3+1
        }
    }
    return -1;//查找无target输出-1；
}
}

Data7.26二分查找

原文：https://www.cnblogs.com/tmtboke/p/15063518.html