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

發表於 分類於 評論數：
文章字數： 992 所需閱讀時間 ≈ 2 分鐘

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

輸入：正整數n

輸出 ：n在S中的位置

原理

輸入值與S陣列的中間值比大小

當輸入值比較大時，接下來只需要判斷S陣列中間值的右邊那一串陣列即可

反之亦然。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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;
            }
        }
    }
}