java - 二分查找算法检查数组中是否包含整数

Question

我在代码中实现二分搜索时遇到问题，您能解释一下它是如何工作的吗？

binarySearch 接受一个整数数组 a 和一个整数 n 并使用 二分查找算法检查n是否包含在a中。如果 n 为，则返回 true 包含在 a 中，并打印做出的决策数和错误数 否则。

import java.util.Arrays;
import java.util.Random;

public class Excersice2 {

    public static void main(String[] args) {
        int[] arr = createArray(10);
        System.out.println("the array not sorted");
        printArray(arr);
        arr = sortArray(arr);
        System.out.println("the array sorted");
        printArray(arr);
        System.out.println(binarySearch(arr,50));

    }

    public static void printArray(int []arr)
    {

        System.out.println(Arrays.toString(arr));

    }

    public static int [] createArray(int n) {
        int[] arr = new int[n];

        Random rand = new Random();
        for(int i = 0; i < n; i++) 
            arr[i] = rand.nextInt(101);

        return arr; 

    }

    public static int[] sortArray(int[] arr) {
        Arrays.sort(arr);
        return arr;

    }

    public static boolean binarySearch(int arr[], int n) {
        int firstIdx = 0;
        int lastIdx = - 1;
        int middle = (firstIdx + lastIdx)/2;
        int idx = arr.length/2;

        while( firstIdx <= lastIdx) {
            if(binarySearch[middle] < arr);

        }


    }

}

结果应该是: 花了2次才发现数组中包含了值50。查看列表时

Answer 1

当您有一个数字数组并且该数组已排序时，您可以使用二分搜索算法。 算法检查键(您要查找的数字)是否等于数组的中间值。 如果是，则搜索完成，并且键位于中间位置。 如果不是，则算法检查键是否大于或小于中间值。 如果它更大，则算法仅在数组的后半部分重复搜索，并将中间的下一个位置作为左侧。 如果较少，则仅在上半场以中场之前的位置为右。 并重复此操作，直到找到键或数组中不再有位置。

调用二分查找方法

//the number you are looking for. For example 4.
int key = 4;
//the first element of array
int left = 0;
//the last element of array
int right = arr.length - 1;
int pos = binarySearch(left, right, key);
if(pos == -1) { System.out.println("Array does not contain key"); }
else { System.out.println("Array contains key at position : " + pos); }

二分查找算法方法

int binarySearch(int left, int right, int key) {

        int pos;
        int mid;

        if(left > right) {
            //there is no more positions to search
            pos = -1;
        } else {
            //Getting the middle position of array
            mid = (left + right) / 2;
            //if the key is the middle positions value
            if(arr[mid] == key)
                pos = mid;
            //if the key is less than the middle value
            else if(key < arr[mid])
                //repeat the search only at the first half of array
                pos = binarySearch(left, mid-1, key);
            else
                //else if the key is greater than the middle value
                //search at the second half of array
                pos = binarySearch(mid+1, right, key);
        }
        return pos; 
    }