詳解二分查找演算法Binary Search

一、binarysearch怎麼讀

Binary Search是一種搜索演算法，也稱為折半搜索。Binary Search是計算機科學中的經典演算法，用於在有序數組中查找某一特定元素的位置。

讀音為 [ˈbaɪn ə ri sɜrtʃ]，中文通常稱之為「二分查找」，「折半查找」或「二分法」，相信大家已經聽過這些辭彙了。

二、binary search方法只能操作

二分查找法只適用於元素有序的情況下，如果是無序的元素需要先進行排序操作，才能使用二分查找演算法。

時間複雜度為O(logN)。與暴力搜索的時間複雜度O(N)相比，二分查找的時間複雜度更小，效率更高。

三、binarysearch()方法的作用

/**
 * Searches the specified array for the specified value using the binary search algorithm.
 * @param  arr   the array to be searched
 * @param  key   the value to be searched for
 * @return       index of the search key, if it is contained in the array;
 *               otherwise, (-(insertion point) - 1). 
 *               The insertion point is defined as the point at which the key would be 
 *               inserted into the array: the index of the first element greater than the key, 
 *               or arr.length if all elements in the array are less than the specified key.
 */
public static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    while (low >> 1;
        int midVal = arr[mid];
        if (midVal  key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

binarySearch()方法是二分查找演算法在Java數組中經典的實現方法。該方法接收一個已經排好序的數組，和需要查找的值，並返回值在數組中的索引位置。如果值不存在於數組中，則返回插入值的索引（可以認為是不存在值的位置）。

四、binarysearch的例子

public static void main(String[] args) {
    int[] nums = {1, 3, 5, 6, 8, 9};
    int target = 6;
    int index = binarySearch(nums, target);
    System.out.println("Index of " + target + " is " + index);
}

上述例子中，我們定義了一個數組nums和一個需要查找的值target，然後調用binarySearch()方法查找target的位置。最終結果顯示target在nums中的索引位置為3。

五、binary search讀法

Binary Search的中文翻譯為「二分查找」，整個過程就是不斷地將數組中間位置的值與目標值進行比較。如果中間位置的值大於目標值，則在數組的左半部分查找，反之則在右半部分查找，直到找到目標值為止。

在英文中，Binary Search的發音是[“ˈbaɪnərɪsɜrtʃ”]，其中Binary的「bi」讀為「baɪ」，Search的「sea”讀為「sɜrʧ」。

六、binary search方法的作用

Binary search是一種高效的查找演算法，常用於處理大數據量的查找操作。二分查找法的時間複雜度為O(logN)，比暴力查找的時間複雜度O(N)效率更高。

在Java中，Arrays類提供了binarySearch()方法，可以方便地對數組進行二分查找操作，應用廣泛。

七、arrays binarysearch

public static void main(String[] args) {
    int[] nums = {1, 3, 5, 6, 8, 9};
    int target = 6;
    int index = Arrays.binarySearch(nums, target);
    System.out.println("Index of " + target + " is " + index);
}

Java中的Arrays類提供了binarySearch()方法，可以快速地查找一個已經排好序的數組中的某個值。

八、binarysearch方法

在Java中，Collections類也提供了binarySearch()方法，可以對已經實現了Comparable介面的對象進行二分查找。

public static void main(String[] args) {
    List nums = new ArrayList();
    nums.add(1);
    nums.add(3);
    nums.add(5);
    nums.add(6);
    nums.add(8);
    nums.add(9);
    int target = 3;
    int index = Collections.binarySearch(nums, target);
    System.out.println("Index of " + target + " is " + index);
}

九、binarysearch演算法

二分查找演算法是一種經典的分治思想的應用，它的基本思路是將一個有序數組不斷地二分，來查找目標元素。由於其時間複雜度非常低，所以被廣泛地應用於各種領域中。

以下是二分查找的經典演算法實現：

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left  target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

上述代碼中，我們首先將sortedArray數組的左右邊界設為0和數組長度-1，然後在while循環中不斷縮小左右邊界的範圍，直到找到目標元素或者發現沒有這個元素為止，最後返回查找結果。