关于微信小程序使用JavaScript实现检索算法

拟解决生活中最常见的问题之一：检索问题（查找问题）

该问题要求在一个列表中查找某个具体元素是否出现，
若出现，返回具体元素在数组中的位置，否则返回-1。根据列表中
元素的相对大小信息，有顺序检索、二分检索、三分检索等算法
思路可供参考使用，并能分析各个算法所使用的算法设计技
术和时间复杂度。下列基本要求必须完成：
1、 设计一个交互界面（例如菜单）供用户选择，如果可能，最好
是一个图形化用户界面；
2、 能够人工输入或随机产生一个长度为 n 的整数数组，要求数组
任意两个元素都互不相同；
3、 设计一个算法判断要求 2 中产生的整数数组是否为或未排序
（输出 0）、升序（输出 1）、降序（输出 2）、先升后降（输出
3）、或先降后升（输出 4）状态；
4、 给定某具体元素，使用顺序检索算法判断该具体元素是否出现
在要求 2 中产生的数组中，并统计关键字比较的次数；
5、 给定某具体元素，使用二分检索算法判断该具体元素是否出现
在要求 2 中产生的升序或降序的数组中，并统计关键字比较的次
数；
6、 给定某具体元素，使用三分检索算法判断该具体元素是否出现
在要求 2 中产生的升序或降序的数组中，并统计关键字比较的次
数；
7、 给定先升后降（或先降后升）数组，使用二分检索思路查找该
数组的最大值（或最小值），并统计关键字比较的次数。

wxml

<view class="con">
  <textarea bindinput="handInputArray" class="inputArray" placeholder="手动输入数组" maxlength="1000" ></textarea>
</view>  
<button class="btn1" type="primary" size="mini">创建</button>
<view class="box1">
  <text class="title">随机生成数组</text>
  <view class="box2">
    <input class="count" bindinput="getInputNumber" placeholder="请输入个数" />
    <button class="btn2" style="height: 60rpx;width: 160rpx;" bindtap="randomArray" type="primary" size="mini">GO</button>
  </view>
  <view class="show_array">{{array}}</view>
</view>
<view class="box1">
  <text>判断输出状态</text>
  <view class="box3">
    <text>{{state}}</text>
    <button class="btn2" type="primary" size="mini" style="height: 60rpx;width: 160rpx;" bindtap="callArraySortAlgorithm">GO</button>
  </view>
</view>
<view class="box1">
  <view class="search">
    <text>检索:</text>
    <input bindinput="getInputSpecialNumber" />
  </view>
  <!-- 顺序检索 -->
  <view class="module">
    <view class="mod">
      <text>是否存在</text>
      <text>{{result1}}</text>
    </view>
    <view class="mod">
      <text>比较次数</text>
      <text>{{count1}}</text>
    </view>
    <button class="btn3" type="primary" size="mini" style="height: 50rpx;;line-height: 50rpx;" bindtap="arrayOrderSearch">顺序检索</button>
  </view>
<!-- 二分检索 -->
  <view class="module">
    <view class="mod">
      <text>是否存在</text>
      <text>{{result2}}</text>
    </view>
    <view class="mod">
      <text>比较次数</text>
      <text>{{count2}}</text>
    </view>
    <button class="btn3" type="primary" size="mini" style="height: 50rpx;;line-height: 50rpx;" bindtap="callBinaryCount">二分检索</button>
  </view>
  <view class="module">
    <view class="mod">
      <text>下标</text>
      <text>{{redex}}</text>
    </view>
    <button class="btn3" type="primary" size="mini" style="height: 50rpx;;line-height: 50rpx;" bindtap="callBinarySearch">检索下标</button>
  </view>
<!-- 三分检索 -->
  <view class="module">
    <view class="mod">
      <text>是否存在</text>
      <text>{{result3}}</text>
    </view>
    <view class="mod">
      <text>比较次数</text>
      <text>{{count3}}</text>
    </view>
    <button class="btn3" type="primary" size="mini" style="height: 50rpx;;line-height: 50rpx;" bindtap="callTernaryCount">三分检索</button>
  </view>
</view>

<view class="box1">
  <text>二分检索先升后降数组最大值</text>
  <view class="box3">
    <text>{{max}}</text>
    <button class="btn2" type="primary" size="mini" bindtap="callArrayUptoDownBinarySearchMax">START</button>
  </view>
</view>
<view class="box1">
  <view>二分检索先降后升数组最小值</view>
  <view class="box3">
    <text>{{min}}</text>
    <button class="btn2" type="primary" size="mini" bindtap="callArrayDowntoUpBinarySearchMin">START</button>
  </view>
</view>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

wxss

page{
  background: #eeeeee;
}
.con{
  width: 740rpx;
  background: #ffffff;
  margin: 14rpx auto;
  border-radius: 12rpx;
}
.inputArray{
  width: 720rpx;
  height: 80rpx; 
  line-height: 40rpx;
  margin:0 auto;
  word-wrap: break-word;
  word-break: break-all;
}
.btn1{
  margin-left: 320rpx;
}
.box1{
  width: 720rpx;
  background: #ffffff;
  margin: 14rpx auto;
  border-radius: 12rpx;
  padding: 10rpx;
}
.title{
  font-size: smaller;
}
.count{
  display: block;
  width: 180rpx;
  height: 70rpx;
  border: #3D4E96 2rpx solid;
  text-align: center;
  border-radius: 10rpx;
}
.btn2{
  display: inline-block;
  margin: 0;
  text-align: center;

}
.box2{
  display: flex;
  justify-content: space-around;
  align-items: center;
  padding: 12rpx 0;
  border-bottom: #eeeeee 8rpx dashed;
}
.show_array{
  min-height: 80rpx;
  width: 720rpx;
  line-height: 40rpx;
  word-wrap: break-word;
  word-break: break-all;
  padding: 12rpx 0;
  letter-spacing: 2rpx;
}
.box3{
  display: flex;
  justify-content: space-around;
  align-items: center;
  padding: 12rpx 0;
}
.box3 text{
  display: inline-block;
  height: 40rpx;
  width: 120rpx;
  text-align: center;
  padding-bottom: 10rpx;
  border-bottom:2rpx solid #000000 ;
}
.search{
  display:flex;
  justify-content: center;
  align-items: center;
}
.search input{
  width: 120rpx;
  border:4rpx solid #eeeeee;
  border-radius: 12rpx;
  margin-left: 14rpx;
  text-align: center;
}
.module{
  width: 700rpx;
  border-radius: 12rpx;
  margin:12rpx auto;
  background-color: rgb(232, 247, 245);
}
.mod{
  padding: 10rpx 60rpx 0;
  height: 44rpx;
  display: flex;
  align-items: center;
}
.mod text:nth-child(2){
  display: inline-block;
  width: 180rpx;
  height: 40rpx;
  border-bottom:2rpx solid #9b9b9b ;
  position: absolute;
  right:150rpx;
  text-align: center;
  padding-bottom: 2rpx;
}
.btn3{
  margin:14rpx 0 10rpx 500rpx;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

js

Page({
  /**
   * 页面的初始数据
   */
  data: {
    array:[],
    maxRandom:10,
    number:'',
    specialNumber:' ',
    state:' ',
    result1:' ',
    count1:' ',
    upORdown1:' ',
    result2:' ',
    count2:' ',
    upORdown2:' ',
    result3:' ',
    count3:' ',
    max:' ',
    min:' ',
    redex:' '
  },
// 输入数组
handInputArray(e) {
  let testarray=e.detail.value
  this.data.array=testarray.split(",")
},
getInputNumber(e){
  this.data.number=e.detail.value
},
getInputSpecialNumber(e){
  this.data.specialNumber=e.detail.value
},
//手动创建数组
artificialArray:function(){
  let array=this.data.array
  this.setData({
    array:array
  })
},
// 产生随机数组
randomArray:function(){
  let number=this.data.number
  let max=this.data.maxRandom
  let i=0,j=0,num=0
  let result=[]
  result[0]=Math.floor(Math.random() *max)
  for(i=1;i<number;i++){
    num=Math.floor(Math.random() * max)
    for(j=0;j<i;j++){
      if(num==result[j]){
        i--
        break;
      }
    }
    if(j==i){
      result[i]=num
    }
  }
  this.setData({
    array:result
  })
},
// 判断是否为升序
isUpSort:function() {
  let array=this.data.array
  for(let i=0;i<array.length-1;i++){
    if(array[i]>array[i+1]){
      return false;
    }
  }
  return true
},
// 判断是否为降序
isDownSort:function(){
  let array=this.data.array
  for(let i=0;i<array.length-1;i++){
    if(array[i]<array[i+1]){
      return false
    }
  }
  return true
},

// 得到数组最大值位置
getMaxIndex:function(){
  let array=this.data.array
  let max=array[0]
  let max_index=0
  for(let i=1;i<array.length;i++){
    if(array[i]>max){
      max=array[i]
      max_index=i
    }
  }
  return max_index
},
// 得到数组最小值位置
getMinIndex:function(){
  let array=this.data.array
  let min=array[0]
  let min_index=0
  for(let i=1;i<array.length;i++){
    if(array[i]<min){
      min=array[i]
      min_index=i
    }
  }
  return min_index
},

// 判断数组是哪种类型
arraySortAlgorithm:function(){
  let array=this.data.array
  if(this.isUpSort()){
    return 1
  }
  if(this.isDownSort()){
    return 2
  }
  let flag=1
  for(let i1=0;i1<array.length-1;i1++){
    if(flag==1 && array[i1]>array[i1+1]){
      flag=3
    }
    if(flag==3 && array[i1]<array[i1+1]){
      flag=0
    }
  }
  if(flag==3){
    return flag
  }
  let flag1=1
  for(let i1=0;i1<array.length-1;i1++){
    if(flag1==1 && array[i1]<array[i1+1]){
      flag1=4
    }
    if(flag1==4 && array[i1]>array[i1+1]){
      flag1=0
    }
  }
  return flag1
},
callArraySortAlgorithm:function(){
  this.setData({
    state:this.arraySortAlgorithm()
  })
},
// 顺序检索
arrayOrderSearch:function(){
  let array=this.data.array
  let number=this.data.specialNumber
  for(let i=0;i<array.length;i++){
    if(array[i]==number){
      this.setData({
        result1:'存在',
        count1:i+1
      })
      return i+1
    }
  }
  this.setData({
    result1:'不存在',
    count1:array.length
  })
  return array.length
},
// 二分检索
binaryCount:function(){
  let nums=this.data.array
  let target=this.data.specialNumber
  let left=0
  let right=nums.length-1
  let count=0
    while(right>=left){
    let index=parseInt((right+left)/2)
    count++
      if(nums[index]==target){
          return count
      }else if(nums[index]<target){
          left=index+1
      }else{
          right=index-1
      }
    }
    this.setData({
            result2:'不存在',
            count2:count+2
          })
    return -1
},
callBinaryCount:function(){
  if(this.binaryCount()==-1){
    return
  }
  else{
    this.setData({
      result2:'存在',
      count2:this.binaryCount()
    })
  }
},
// 返回下标
binarySearch:function(){
  let nums=this.data.array
  let target=this.data.specialNumber
  let left=0
  let right=nums.length-1
    while(right>=left){
    let index=parseInt((right+left)/2)
      if(nums[index]==target){
          return index
      }else if(nums[index]<target){
          left=index+1
      }else{
          right=index-1
      }
    }
    return -1
},
callBinarySearch:function(){
  if(this.binarySearch()==-1){
    this.setData({
      redex:' '
    })
  }
  else{
    this.setData({
      redex:this.binarySearch()
    })
  }
},

// 三的倍数
ternaryCount:function(){
  let array=this.data.array  
  let key=this.data.specialNumber
  let mid1 = 0;
  let mid2 = 0;
  let low = 0;
  let high = array.length;
  let count=0
  while(low <= high){
      mid1 = (high -low)/3+low;
      mid2 = 2*(high -low)/3+low;
      count++
      if(array[low]>key || array[high-1]<key){
          break;
      }
      else if(array[mid1] == key) {
          return count
      }
      else if(array[mid2] == key) {
          return count
      }
      else if(array[mid1] > key)
        high= mid1;
      else if(array[mid1] < key && array[mid2] > key){
         low = mid1;
         high = mid2;
      }
      else low = mid2;
     }
     this.setData({
      result3:'不存在',
      count3:count+2
    })
      return -1;
},
callTernaryCount:function(){
  if(this.ternaryCount()==-1){
    return
  }
  else{
    this.setData({
      result3:'存在',
      count3:this.ternaryCount()
    })
  }
},

//二分检索求先升后降数组最大值
// 个数需为奇数
arrayUptoDownBinarySearchMax:function(){
  let array=this.data.array
  let left = 0;
  let right = array.length - 1;
  while (left <= right) {
    let mid = (left + right) / 2;
    if (array[mid] > array[mid - 1] && array[mid] > array[mid + 1]) {
        return array[mid];
    } else if (array[mid] < array[mid - 1]) {
        right = mid - 1;
    } else if (array[mid] < array[mid + 1]) {
        left = mid + 1;
    }
  }
  return -1;
},
callArrayUptoDownBinarySearchMax:function(){
  this.setData({
    max:this.arrayUptoDownBinarySearchMax()
  })
},
//二分检索求先降后升数组最小值
// 个数需为奇数
arrayDowntoUpBinarySearchMin:function(){
  let array=this.data.array
  let left = 0;
  let right = array.length - 1;
  while (left <= right) {
      let mid = (left + right) / 2;
      if (array[mid] < array[mid - 1] && array[mid] < array[mid + 1]) {
          return array[mid];
      } else if (array[mid] > array[mid - 1]) {
          right = mid - 1;
      } else if (array[mid] > array[mid + 1]) {
          left = mid + 1;
      }
  }
  return -1;
},
callArrayDowntoUpBinarySearchMin:function(){
  this.setData({
    min:this.arrayDowntoUpBinarySearchMin()
  })
},
  /**
   * 生命周期函数--监听页面加载
   */
  onLoad(options) {

  },
})
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334