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

2023-11-18

检索算法

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

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

该问题要求在一个列表中查找某个具体元素是否出现，
若出现，返回具体元素在数组中的位置，否则返回-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>

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;
}

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) {

  },
})

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)