如何在数组中的项目值和项目索引之间切换以计算变量？

Question

我的程序计算用户超过指定温度的天数。我正在使用二进制搜索并需要计算中点，但我无法在数组项值和数组索引之间切换。当值高于 mid 时，我将 start 设置为 mid + 1 但 mid 然后被重新分配为其先前的值。我应该怎么做？我试过

var mid = Math.floor(janMax(end) - janMax(start) / 2);

不行。

这是我的二进制搜索函数：

function binarySearchAbove(end, value){
    var start = janMax[0];
    var end = janMax[30];
    var count = "";
    console.log(end);//53, works
    var value = listInput.value;

    while (value <= end){
        var average = Math.floor(janMax.length / 2);
        var mid = janMax[average];
        console.log(average);
        console.log(mid);//44
        console.log(start);//45

        for (i = 0; i < janMax.length; i++){
            if(value == janMax[i]){
            break;
            console.log(i);//gives correct value    
            }
        }

        if (value < mid){
            start++;
            console.log(start);//37

        }   else if (value > mid){
            start = mid + 1;
            console.log(start);//45

        }
        if (value == mid || value == start){
            count = janMax.length - i;//0
            console.log(i);//gives 31
            alert("There were " + count + " days above " + value + " degrees.");
            break;
        }   

        if (value <= start){
            alert("Every day was above " + value + " degrees.");
            break;

        }   else if (value >= end){
            alert("There were no days above " + value + " degrees.");
            break;
        }
    }
}

var janMax = [36, 37, 38, 38, 39, 39, 39, 39, 40, 40, 40, 41, 42, 44, 44, 44, 46, 46, 47, 47, 47, 47, 47, 48, 48, 49, 49, 50, 50, 53, 53];

Answer 1

我的意思是最简单的答案是这样，但这不是您想要的二进制搜索：

const janMax = [36, 37, 38, 38, 39, 39, 39, 39, 40, 40, 40, 41, 42, 44, 44, 44, 46, 46, 47, 47, 47, 47, 47, 48, 48, 49, 49, 50, 50, 53, 53];

function searchAbove(value) {
    return janMax.reduce((count, curr) => curr > value ? count + 1 : count, 0);
}

console.log(searchAbove(44));

但这将是二进制搜索的实现：

var janMax = [36, 37, 38, 38, 39, 39, 39, 39, 40, 40, 40, 41, 42, 44, 44, 44, 46, 46, 47, 47, 47, 47, 47, 48, 48, 49, 49, 50, 50, 53, 53];

function binarySearchAbove(value) {
  if (value < janMax[0]) {
    alert("Every day was above " + value + " degrees.");
    return;
  } else if (value >= janMax[janMax.length - 1]) {
    alert("There were no days above " + value + " degrees.");
    return;
  }

  let count = 0;

  function countHigherValues(values) {
    if (values.length == 0) {
      return;
    }

    const midIndex = Math.floor(values.length / 2);

    if (value > values[midIndex]) {
      countHigherValues(values.slice(midIndex));
    } else {
      let currIndex = midIndex;
      while (currIndex >= 0 && values[currIndex] > value) {
        currIndex--;
      }

      currIndex++;
      while (currIndex < values.length && values[currIndex] >= value) {
        if (values[currIndex] > value) {
          count++;
        }

        currIndex++;
      }
    }
  }

  countHigherValues(janMax);

  alert("There were " + count + " days above " + value + " degrees.");
}

binarySearchAbove(43);
binarySearchAbove(59);
binarySearchAbove(29);

Answer 2

你有 5 个测试用例。值 < 开始，值 > 结束，值 < 中值，值 > 中值，值 = 中值。您还必须考虑何时您的价值不在 arra 中而是在开始和结束之间。

下面使用你的二分查找

document.getElementById("submit").addEventListener("click", binarySearchAbove);
var listInput = document.getElementById('guess')
var janMax = [36, 37, 38, 38, 39, 39, 39, 39, 40, 40, 40, 41, 42, 44, 44, 44, 46, 46, 47, 47, 47, 47, 47, 48, 48, 49, 49, 50, 50, 53, 53];

function binarySearchAbove(event){
event.preventDefault();
    var start = janMax[0];
    var sidx = 0;
    var eidx = 30;
    var end = janMax[30];
    var count = 0;    
    var guess = listInput.value;   
    var guess2 = guess
    var midx = Math.floor(janMax.length / 2);
        var mid = janMax[midx];   
                
        
        if (guess < start){
            midx = 0;
            guess = end + 1;        
        }else if (guess > end){
            midx = janMax.length+1
            guess = end + 1
        }
        

    while (guess <= end){  
    
        if(guess == mid){
        
           while (guess == janMax[midx]){
                 midx++                
           }           
           guess= end+1;      
                
        }else if(guess < mid ){           
           eidx = midx;
           end=janMax[eidx]
           midx = Math.floor((sidx+eidx)/2  )
           mid=janMax[midx]
           
              if(sidx == midx){
                midx=eidx 
                guess = end +1
              } 
        }else if(guess > mid  ){
           sidx = midx
           start=janMax[sidx]
           midx=Math.floor((sidx+eidx)/2  )
           mid=janMax[midx]
           
            if(sidx == midx){
              midx=eidx
              guess = end + 1 //probably not needed
              } 
        }
    }
        
        
        
        var days = janMax.length - midx 
        if (days > 0 && days != janMax.length){ 
            alert("There were " + days + " days above " + guess2 + " degrees.");            
        }   

        if (days == janMax.length){
            alert("Every day was above " + guess2 + " degrees.");           

        }   else if (days == 0){
            alert("There were no days above " + guess2 + " degrees.");
            
        }  
    
}

<input type='number' id = 'guess'>
<input type='submit' id='submit' value='submit'>

<div>
36, 37, 38, 38, 39, 39, 39, 39, 40, 40, 40, 41, 42, 44, 44, 44, 46, 46, 47, 47, 47, 
00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 
47, 47, 48, 48, 49, 49, 50, 50, 53, 53<br>
21, 22, 23, 24, 25, 26, 27, 28, 29, 30
</div>

如何在数组中的项目值和项目索引之间切换以计算变量？

How to switch between item value in an array and item index to calculate a variable?

javascript

search

binary-search