Java 互動式和遞迴式二叉搜尋

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 二叉搜尋演算法的迭代實現
  2. Java 二叉搜尋的迭代程式
  3. 遞迴二叉搜尋演算法
  4. Java 二叉搜尋的遞迴程式
  5. Arrays.binarySearch() 概述
  6. Java 二叉搜尋程式
Java 互動式和遞迴式二叉搜尋
注意
如果你想詳細瞭解二叉搜尋,那麼可以參考二叉搜尋演算法一文。

二叉搜尋演算法的迭代實現

假設我們有一個未排序的陣列 A[],包含 n 個元素,我們想找到一個元素 X

  • lo0hin - 1
  • lo< hi
    • 設定 mid=lo + (hi - lo)/2
    • 如果 A[mid] == X,我們找到了元素,返回索引 mid
    • 如果 A[mid] < X,則丟棄左半部分元素,並將 lo 設為 mid+1
    • 否則,如果 A[mid] > X,則丟棄右半部分元素,並將 hi 設為 mid-1
  • 未找到元素,所以返回 -1

Java 二叉搜尋的迭代程式

class BinarySearch {
    int binarySearch(int arr[], int x)
    {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;

            if (arr[mid] == x)
                return mid;

            if (arr[mid] < x)
                lo = mid + 1;

            else
                hi = mid - 1;
        }
        return -1;
    }

    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = { 1, 2, 3, 4, 5 };
        int n = arr.length;
        int x = 5;
        int position = ob.binarySearch(arr, x);
        if (position == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at index: " + position);
    }
}

輸出:

Element found at index: 4

遞迴二叉搜尋演算法

假設我們有一個無序陣列 A[],包含 n 個元素,我們想找到一個元素 X

  • 初始化 lo0hin-1
  • 如果 lo>hi,說明我們已經用盡了陣列的搜尋空間,返回-1。
  • 計算中點 midlo+(hi-lo)/2。它將陣列分為兩部分:下半部分是 0mid - 1 的元素,上半部分是 midn - 1 的元素。
  • 如果 X=mid,我們發現目標元素返回 mid
  • 如果 X 小於 mid,通過遞迴呼叫 binarysearch(arr, lo, mid-1) 搜尋陣列的下半部分。
  • Else 如果 X 大於 mid,則通過遞迴呼叫 binarysearch(arr, mid+1, hi) 來搜尋陣列的上半部分。

Java 二叉搜尋的遞迴程式

class BinarySearch {
    int binarySearch(int arr[], int lo, int hi, int x) {
        if (hi >= lo && lo < arr.length - 1) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binarySearch(arr, lo, mid - 1, x);
            return binarySearch(arr, mid + 1, hi, x);
        }
        return -1;
    }
    public static void main(String args[]) {
        BinarySearch ob = new BinarySearch();
        int arr[] = { 1, 2, 3, 4, 5 };
        int n = arr.length;
        int x = 2;
        int position = ob.binarySearch(arr, 0, n - 1, x);
        if (position == -1)
            System.out.println("Element not found !!!");
        else
            System.out.println("Element found at index: " + position);
    }
}

輸出:

Element found at index: 1

Arrays.binarySearch() 概述

Java 為我們提供了一個現成的函式 Arrays.binarySearch(),這樣我們就不用自己去實現這個函式了。它是一個非常簡單易用且有效實現的方法,而且不容易出錯。

語法

public static int binarySearch(T arr, T key )

T 可以是下列任何一種。int, float, short, long, byte, char, double, 甚至還有使用者定義的 Object

就像我們實現的二叉搜尋一樣,它也要求對陣列進行排序,否則結果是無法定義的。它使用二叉搜尋演算法對陣列進行搜尋,找到目標元素的索引。如果目標元素有多個出現,那麼它可以返回其中任何一個元素的索引。

引數

Arr 輸入陣列
Key 我們要搜尋的目標元素。

返回值

如果它找到了目標元素,那麼就返回它的索引,否則就返回 beg - 1,其中 beg 是陣列搜尋空間的起始索引。否則,它返回 beg - 1,其中 beg 是陣列搜尋空間的起始索引。

Java 二叉搜尋程式

import java.util.Arrays;

class BinarySearchExample{
    public static void main(String args[]){
        int arr[] = {1,2,3,4,5};
        int key = 2;
        int result = Arrays.binarySearch(arr,key);
        if (result < 0)
            System.out.println("Element is not found!");
        else
            System.out.println("Element is found at index: "+result);
    }
}

輸出:

Element is found at index: 1
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Java Algorithm