From 6b1e587424463b3965c55c5949812c78c965dd58 Mon Sep 17 00:00:00 2001
From: chai <chaifix@163.com>
Date: Wed, 23 Jun 2021 18:26:05 +0800
Subject: *misc

---
 Assets/Algorithms/Searching/SearchingHelper.cs | 113 ++++++++++++++++++++-----
 1 file changed, 92 insertions(+), 21 deletions(-)

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

diff --git a/Assets/Algorithms/Searching/SearchingHelper.cs b/Assets/Algorithms/Searching/SearchingHelper.cs
index a36e653..191ff5e 100644
--- a/Assets/Algorithms/Searching/SearchingHelper.cs
+++ b/Assets/Algorithms/Searching/SearchingHelper.cs
@@ -34,7 +34,7 @@ namespace AlgorithmCollection.Searching
         public static int BinarySearch<T>(List<T> data, T value) where T : IComparable, IEquatable<T>
         {
             int index = -1;
-            RecursionHelper.DivideAndConquer(
+            RecursionHelper.DNC(
                 () => 
                 {
                     DivisionDescriptor div = new DivisionDescriptor();
@@ -42,24 +42,16 @@ namespace AlgorithmCollection.Searching
                     div.right = data.Count - 1;
                     return div;
                 },
-                (DivisionDescriptor div) =>
-                {
-                    if (data[div.left].CompareTo(value) == 0)
-                    {
-                        index = div.left;
-                    }
-                },
-                (DivisionDescriptor div, out bool bAdhoc) =>
+                (DivisionDescriptor div, out DivisionDescriptor[] division) =>
                 {
                     int left = div.left;
                     int right = div.right;
-                    DivisionDescriptor[] division = new DivisionDescriptor[1];
+                    division = new DivisionDescriptor[1];
                     if(right <= left)
                     {
                         division[0].left = left;
                         division[0].right = right;
-                        bAdhoc = true;
-                        return division;
+                        return true;
                     }
                     int mid = (left + right) / 2;
                     T midValue = data[mid];
@@ -77,13 +69,18 @@ namespace AlgorithmCollection.Searching
                     {
                         division[0].left = mid;
                         division[0].right = mid;
-                        bAdhoc = true;
-                        return division;
+                        return true;
                     }
-                    bAdhoc = false;
-                    return division;
-                }
-                );
+                    return false;
+                },
+				(DivisionDescriptor div) =>
+				{
+					if (data[div.left].CompareTo(value) == 0)
+					{
+						index = div.left;
+					}
+				}
+				);
             return index;
         }
 
@@ -113,10 +110,84 @@ namespace AlgorithmCollection.Searching
 			return min;
 		}
 
-
-		public static T Select_Random<T>(IList<T> data, bool descent = false) where T : IList, IComparable
+		// 找到第n大或者第n小，类比快速排序
+        // O(n)
+		public static bool Select<T>(IList<T> data, int n, bool bMin, ref T findValue) where T : IComparable
 		{
-			return default(T);
+            bool suc = false;
+			T v = default(T);
+			RecursionHelper.DNC(
+			()=>
+			{
+				DivisionDescriptor div = new DivisionDescriptor();
+				div.left = 0;
+				div.right = data.Count - 1;
+				div.userdata = n;
+				return div;
+			},
+			(DivisionDescriptor division, out DivisionDescriptor[] div) =>
+			{
+                div = new DivisionDescriptor[1];
+                int left = division.left;
+				int right = division.right;
+				int remain = (int)division.userdata;
+				if(right <= left)
+				{
+                    div[0].left = left;
+                    div[0].right = right;
+                    div[0].userdata = remain;
+                    return true;
+				}
+				int l = left;
+				int r = right + 1;
+				T val = data[l];
+				while (true)
+				{
+					while ((bMin && data[++l].CompareTo(val) <= 0 || !bMin && data[++l].CompareTo(val) >= 0) && l < right);
+					while ((bMin && data[--r].CompareTo(val) >= 0 || !bMin && data[--r].CompareTo(val) <= 0) && r > left);
+					if (l >= r)
+						break;
+					Algorithms.Swap(ref data, l, r);
+				}
+				Algorithms.Swap(ref data, left, r);
+				int count = r - left + 1;
+				if(count > remain)
+				{
+					div[0].left = left;
+					div[0].right = r - 1;
+					div[0].userdata = remain;
+				}
+				else if(count < remain)
+				{
+					div[0].left = r + 1;
+					div[0].right = right;
+					div[0].userdata = remain - count;
+				}
+				else
+				{
+                    div[0].left = r;
+                    div[0].right = r;
+                    div[0].userdata = 0;
+                    return true;
+                }
+                return false;
+			},
+			(DivisionDescriptor division)=>
+			{
+                if((int)division.userdata == 0)
+                {
+                    int i = division.left;
+                    v = data[i];
+                    suc = true;
+                }
+            }
+			);
+            if (suc)
+            {
+                findValue = v;
+                return true;
+            }
+			return false;
 		}
 
 	}
-- 
cgit v1.1-26-g67d0