#1535 No binary search in JavaScript

Yuri Strot Tue 17 May 2011

Could you please add it?

diff -r 00ef87ea4591 src/sys/js/fan/List.js
--- a/src/sys/js/fan/List.js	Mon Apr 25 15:51:45 2011 -0400
+++ b/src/sys/js/fan/List.js	Tue May 17 19:01:54 2011 +0700
@@ -720,11 +720,7 @@
 fan.sys.List.prototype.sort = function(f)
 {
   this.modify();
-  if (f === undefined) f = null;
-  if (f != null)
-    this.m_values.sort(function(a,b) { return f.call(a,b) });
-  else
-    this.m_values.sort(function(a,b) { return fan.sys.ObjUtil.compare(a,b,false) });
+  this.m_values.sort(fan.sys.List.comparator(f));
   return this;
 }
 
@@ -739,6 +735,28 @@
   return this;
 }
 
+fan.sys.List.prototype.binarySearch = function(key, f)
+{
+  var c = fan.sys.List.comparator(f);
+  var low = 0;
+  var high = this.m_size - 1;
+  while (low <= high)
+  {
+    var mid = (low + high) / 2
+    var cmp = c(this.m_values[mid], key);
+    if (cmp < 0) low = mid + 1;
+    else if (cmp > 0) high = mid - 1;
+    else return mid;
+  }
+  return -(low + 1);
+}
+
+fan.sys.List.comparator = function(f)
+{
+  if (f) return function(a,b) { return f.call(a,b) };
+  return function(a,b) { return fan.sys.ObjUtil.compare(a,b,false) };
+}
+
 fan.sys.List.prototype.reverse = function()
 {
   this.modify();

andy Tue 17 May 2011

Great - thanks Yuri! Pushed with a tweak to truncate the division:

var mid = Math.floor((low + high) / 2);

And looks good:

$ fan compilerJs::TestRunner testSys::ListTest.testBinarySearch

-- Run: testSys::ListTest.testBinarySearch...
   Pass: testSys::ListTest.testBinarySearch  [159]

Time: 179ms

***
*** All tests passed! [1 tests, 1 methods, 159 verifies]
***

Yuri Strot Tue 17 May 2011

Thanks a lot!

Login or Signup to reply.