折半查找演算法

前言

最近要考試了，重新回顧一下之前學的演算法，今天是折半查找，它的平均比較次數是Log2 n

思想

給定一個有序數組A[0..n-1],和查找值K，返回K在A中的下標。

折半查找需要指定3個指針，left、right、mid，分別是左指針指向下標0，右指針指向元素末尾，mid中間值指向（left+right）/ 2向下取整。

如果A[mid] > K,中間值大於要找的K值，移動right指針，right = mid - 1

如果A[mid] < k,中間值小於要找的K值，移動left指針，left = mid + 1

如果A[mid] == K,則返回 mid

演算法實現

public static void Main(string[] args){
    int[] A = {1,2,3,6,7,11,23,56};
    int K = 23;
    Console.WriteLine(Search(A,K));
}
public static int Search(int[] A,int K){
    int left = 0;
    int right = A.Length - 1;
    while(left <= right){
        int mid = (left + right) / 2;
        if(A[mid] == K){ return mid;}
        else if(A[mid]>K){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return -1;
}

結尾

有任何錯誤歡迎指正.