From 8938c3447d88e31f77f20553ed185fc8e64c9ac8 Mon Sep 17 00:00:00 2001
From: chai <chaifix@163.com>
Date: Tue, 22 Jun 2021 14:58:53 +0800
Subject: +misc

---
 Assets/Algorithms/Searching/SearchingHelper.cs | 124 +++++++++++++++++++++++++
 1 file changed, 124 insertions(+)
 create mode 100644 Assets/Algorithms/Searching/SearchingHelper.cs

(limited to 'Assets/Algorithms/Searching/SearchingHelper.cs')

diff --git a/Assets/Algorithms/Searching/SearchingHelper.cs b/Assets/Algorithms/Searching/SearchingHelper.cs
new file mode 100644
index 0000000..1605b43
--- /dev/null
+++ b/Assets/Algorithms/Searching/SearchingHelper.cs
@@ -0,0 +1,124 @@
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using AlgorithmCollection;
+using AlgorithmCollection.Recursion;
+
+namespace AlgorithmCollection.Searching
+{
+
+	public static class SearchingHelper
+	{
+
+		// 二分搜索，返回索引号
+		// O(logn)
+		public static int BinarySearch<T>(T[] dataList, T value) where T : IComparable, IEquatable<T>
+		{
+			int n = dataList.Length;
+			int left = 0;
+			int right = n - 1;
+			while (left <= right)
+			{
+				int middle = (right + left) / 2;
+				T midValue = dataList[middle];
+				if (value.Equals(midValue))
+					return middle;
+				if (value.CompareTo(midValue) > 0)
+					left = middle + 1;
+				if (value.CompareTo(midValue) < 0)
+					right = middle - 1;
+			}
+			return -1; // 没找到
+		}
+
+        public static int BinarySearch<T>(List<T> dataList, T value) where T : IComparable, IEquatable<T>
+        {
+            int index = -1;
+            RecursionHelper.DivideAndConquer(dataList,
+                (IList<T> data) => 
+                {
+                    DivisionDescriptor div = new DivisionDescriptor();
+                    div.left = 0;
+                    div.right = data.Count - 1;
+                    return div;
+                },
+                (IList<T> data, DivisionDescriptor div) =>
+                {
+                    if (data[div.left].CompareTo(value) == 0)
+                    {
+                        index = div.left;
+                    }
+                },
+                (IList<T> data, DivisionDescriptor div, out bool bAdhoc) =>
+                {
+                    int left = div.left;
+                    int right = div.right;
+                    DivisionDescriptor[] division = new DivisionDescriptor[1];
+                    if(right <= left)
+                    {
+                        division[0].left = left;
+                        division[0].right = right;
+                        bAdhoc = true;
+                        return division;
+                    }
+                    int mid = (left + right) / 2;
+                    T midValue = data[mid];
+                    if(midValue.CompareTo(value) > 0)
+                    {
+                        division[0].left = left;
+                        division[0].right = mid - 1;
+                    }
+                    else if (midValue.CompareTo(value) < 0)
+                    {
+                        division[0].left = mid + 1;
+                        division[0].right = right;
+                    }
+                    else
+                    {
+                        division[0].left = mid;
+                        division[0].right = mid;
+                        bAdhoc = true;
+                        return division;
+                    }
+                    bAdhoc = false;
+                    return division;
+                }
+                );
+            return index;
+        }
+
+		// 查找最大值
+		// O(n)
+		public static int FindMax<T>(IList<T> dataList) where T : IList, IComparable
+		{
+			int max = 0;
+			for(int i = 0; i < dataList.Count; ++i)
+			{
+				if (dataList[i].CompareTo(dataList[max]) > 0)
+					max = i;
+			}
+			return max;
+		}
+
+		// 查找最小值
+		// O(n)
+		public static int FindMin<T>(IList<T> dataList) where T : IList, IComparable
+		{
+			int min = 0;
+			for (int i = 0; i < dataList.Count; ++i)
+			{
+				if (dataList[i].CompareTo(dataList[min]) < 0)
+					min = i;
+			}
+			return min;
+		}
+
+
+		public static T Select_Random<T>(IList<T> data, bool descent = false) where T : IList, IComparable
+		{
+			return default(T);
+		}
+
+	}
+
+}
\ No newline at end of file
-- 
cgit v1.1-26-g67d0