Changeset 7cd5878

Timestamp:

Jul 28, 2009, 10:12:06 PM (15 years ago)

Author:

David Benjamin <davidben@mit.edu>

Branches:

master, release-1.10, release-1.4, release-1.5, release-1.6, release-1.7, release-1.8, release-1.9

Children:

d4ecc78

Parents:

f80ada8

git-author:

David Benjamin <davidben@mit.edu> (07/28/09 20:13:03)

git-committer:

David Benjamin <davidben@mit.edu> (07/28/09 22:12:06)

Message:

Implement binary search in dict.c

Just because there's a TODO and it was asking for it.

Signed-off-by: David Benjamin <davidben@mit.edu>

File:

• dict.c (modified) (2 diffs)

dict.c

@@ -3 +3 @@
  * Stores as a sorted list of key/value pairs.
  * O(n) on inserts and deletes.
- * O(n) on searches, although it should switch to a binary search for O(log n)
+ * O(log n) on searches
  */
 
@@ -30 +30 @@
 /* Finds the position of an element with key k, or of the element where
  * this element would logically go, and stores the index in pos.
- * TODO: optimize to do a binary search.
  * Returns 1 if found, else 0. */
 int _owl_dict_find_pos(owl_dict *d, char *k, int *pos) {
-  int i;
-  for (i=0; (i<d->size) && strcmp(k,d->els[i].k)>0; i++);
-  *pos = i;
-  if (i>=d->size || strcmp(k,d->els[i].k)) {
-    return(0);
-  } else {
-    return(1);
+  int lo, hi, mid, cmp;
+  lo = 0;
+  hi = d->size;
+  while (lo < hi) {
+    mid = (lo+hi)/2; // lo goes up and we can't hit hi, so no +1
+    cmp = strcmp(k, d->els[mid].k);
+    if (cmp == 0) {
+      lo = hi = mid;
+    } else if (cmp < 0) {
+      hi = mid;
+    } else { // cmp > 0
+      lo = mid+1;
+    }
   }
+  *pos = lo;
+  return !!(lo < d->size && !strcmp(k, d->els[lo].k));
 }