# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1569488302 -7200
# Node ID 46c9a731a686e67ffb45882c38ecb969b241aefc
# Parent  e0d04cd8f992e0500a6fb57e5fd96b905b36ae56
Use custom binary search in triangle indices.

diff -r e0d04cd8f992 -r 46c9a731a686 cmd/isoareas/main.go
--- a/cmd/isoareas/main.go	Wed Sep 25 22:01:05 2019 +0200
+++ b/cmd/isoareas/main.go	Thu Sep 26 10:58:22 2019 +0200
@@ -19,7 +19,6 @@
 	"log"
 	"math"
 	"os"
-	"sort"
 	"strconv"
 	"strings"
 	"time"
@@ -165,16 +164,29 @@
 	return t.Halfedges[idx : idx+3]
 }
 
+func contains(needle int32, haystack []int32) bool {
+	lo, hi := 0, len(haystack)-1
+	for lo <= hi {
+		mid := (hi-lo)/2 + lo
+		switch v := haystack[mid]; {
+		case v < needle:
+			lo = mid + 1
+		case v > needle:
+			hi = mid - 1
+		default:
+			return true
+		}
+	}
+	return false
+}
+
 func inner(t *octree.Triangulation, idx int32, indices []int32) bool {
 
 	for _, n := range neighbors(t, idx) {
 		if n < 0 {
 			return false
 		}
-		n /= 3
-		if p := sort.Search(len(indices), func(i int) bool {
-			return indices[i] >= n
-		}); p >= len(indices) || indices[p] != n {
+		if !contains(n/3, indices) {
 			return false
 		}
 	}