【演算法實作筆記】二分搜尋法 C#實作in Unity

用以搜尋已排序的一串資料，由小排到大

輸入：正整數n
輸出 ：n在S中的位置

原理
輸入值與S陣列的中間值比大小
當輸入值比較大時，接下來只需要判斷S陣列中間值的右邊那一串陣列即可
反之亦然。

using UnityEngine;
using System.Collections;

public class BinarySearch_ : MonoBehaviour {

    public int middle;
    int[] hi = new int[5]{1,2,3,4,5};
    void Start()
    {
        middle = Location (hi, 0, 5, 3);
        binarysearch (hi, 2);
    }
    //遞迴版 二元搜尋
    //遞迴呼叫時如果不改變質卻傳進去會消耗很多變數的地址
    int Location(int[] data,int low , int high,int search)
    {

        int mid;

        if (low > high)
            return 0;
        else {
            mid = (low + high) / 2;

            if (search == data [mid])
                return mid;
            else if (search <= data [mid])
                return Location (data, low, mid - 1, search);
            else
                return Location (data, mid + 1, high,search);
                
        }

    }
    //普通版
    void binarysearch(int[] data,int search)
    {
        int low = 0;
        int high = data.Length;

        while (low <= high) {
            int mid = (low+high) / 2;
            if (data [mid] == search) {
                Debug.Log ("key" + mid);
                return;
            } else if (data [mid] > search) {
                high = mid - 1;
            } else if (data [mid] < search) {
                low = mid + 1;
            }
        }
    }
}

用UNITY實作，分遞迴跟普通版，多研究就能看出來了。

Share: