1 /******************************************************************************
2 * Copyright 1998-2019 Lawrence Livermore National Security, LLC and other
3 * HYPRE Project Developers. See the top-level COPYRIGHT file for details.
4 *
5 * SPDX-License-Identifier: (Apache-2.0 OR MIT)
6 ******************************************************************************/
7
8 #include "_hypre_utilities.h"
9
10 /*--------------------------------------------------------------------------
11 * hypre_BinarySearch
12 * performs a binary search for value on array list where list needs
13 * to contain ordered nonnegative numbers
14 * the routine returns the location of the value or -1
15 *--------------------------------------------------------------------------*/
16
hypre_BinarySearch(HYPRE_Int * list,HYPRE_Int value,HYPRE_Int list_length)17 HYPRE_Int hypre_BinarySearch(HYPRE_Int *list, HYPRE_Int value, HYPRE_Int list_length)
18 {
19 HYPRE_Int low, high, m;
20 HYPRE_Int not_found = 1;
21
22 low = 0;
23 high = list_length-1;
24 while (not_found && low <= high)
25 {
26 m = (low + high) / 2;
27 if (value < list[m])
28 {
29 high = m - 1;
30 }
31 else if (value > list[m])
32 {
33 low = m + 1;
34 }
35 else
36 {
37 not_found = 0;
38 return m;
39 }
40 }
41 return -1;
42 }
43
44 /*--------------------------------------------------------------------------
45 * hypre_BigBinarySearch
46 * performs a binary search for value on array list where list needs
47 * to contain ordered nonnegative numbers
48 * the routine returns the location of the value or -1
49 *--------------------------------------------------------------------------*/
50
hypre_BigBinarySearch(HYPRE_BigInt * list,HYPRE_BigInt value,HYPRE_Int list_length)51 HYPRE_Int hypre_BigBinarySearch(HYPRE_BigInt *list, HYPRE_BigInt value, HYPRE_Int list_length)
52 {
53 HYPRE_Int low, high, m;
54 HYPRE_Int not_found = 1;
55
56 low = 0;
57 high = list_length-1;
58 while (not_found && low <= high)
59 {
60 m = low + (high-low) / 2;
61 if (value < list[m])
62 {
63 high = m - 1;
64 }
65 else if (value > list[m])
66 {
67 low = m + 1;
68 }
69 else
70 {
71 not_found = 0;
72 return m;
73 }
74 }
75 return -1;
76 }
77
78 /*--------------------------------------------------------------------------
79 * hypre_BinarySearch2
80 * this one is a bit more robust:
81 * avoids overflow of m as can happen above when (low+high) overflows
82 * lets user specify high and low bounds for array (so a subset
83 of array can be used)
84 * if not found, then spot returns where is should be inserted
85
86 *--------------------------------------------------------------------------*/
87
hypre_BinarySearch2(HYPRE_Int * list,HYPRE_Int value,HYPRE_Int low,HYPRE_Int high,HYPRE_Int * spot)88 HYPRE_Int hypre_BinarySearch2(HYPRE_Int *list, HYPRE_Int value, HYPRE_Int low, HYPRE_Int high, HYPRE_Int *spot)
89 {
90
91 HYPRE_Int m;
92
93 while (low <= high)
94 {
95 m = low + (high - low)/2;
96
97 if (value < list[m])
98 high = m - 1;
99 else if (value > list[m])
100 low = m + 1;
101 else
102 {
103 *spot = m;
104 return m;
105 }
106 }
107
108 /* not found (high = low-1) - so insert at low */
109 *spot = low;
110
111 return -1;
112 }
113
114 /*--------------------------------------------------------------------------
115 * Equivalent to C++ std::lower_bound
116 *--------------------------------------------------------------------------*/
117
hypre_LowerBound(HYPRE_Int * first,HYPRE_Int * last,HYPRE_Int value)118 HYPRE_Int *hypre_LowerBound( HYPRE_Int *first, HYPRE_Int *last, HYPRE_Int value )
119 {
120 HYPRE_Int *it;
121 HYPRE_Int count = last - first, step;
122
123 while (count > 0) {
124 it = first; step = count/2; it += step;
125 if (*it < value) {
126 first = ++it;
127 count -= step + 1;
128 }
129 else count = step;
130 }
131 return first;
132 }
133 /*--------------------------------------------------------------------------
134 * Equivalent to C++ std::lower_bound
135 *--------------------------------------------------------------------------*/
136
hypre_BigLowerBound(HYPRE_BigInt * first,HYPRE_BigInt * last,HYPRE_BigInt value)137 HYPRE_BigInt *hypre_BigLowerBound( HYPRE_BigInt *first, HYPRE_BigInt *last, HYPRE_BigInt value )
138 {
139 HYPRE_BigInt *it;
140 HYPRE_BigInt count = last - first, step;
141
142 while (count > 0) {
143 it = first; step = count/2; it += step;
144 if (*it < value) {
145 first = ++it;
146 count -= step + 1;
147 }
148 else count = step;
149 }
150 return first;
151 }
152