Phần tử xuất hiện hơn 1/4 lần trong mảng JavaScript

Mô tả vấn đề

Hàm JavaScript nhận vào mảng số nguyên đã sắp xếp tăng dần arr. Có đúng một số nguyên trong mảng xuất hiện nhiều hơn 25% (một phần tư) số lần, hàm trả về số đó.

Ví dụ, nếu đầu vào là:

const arr = [3, 5, 5, 7, 7, 7, 7, 8, 9];

Thì đầu ra nên là:

const output = 7;

Ví dụ minh họa

Mã thực hiện (tìm kiếm nhị phân):

const arr = [3, 5, 5, 7, 7, 7, 7, 8, 9]; 
const oneFourthElement = (arr = []) => { 
  const len = arr.length / 4; 
  const search = (left, right, target, direction = 'left') => { 
    let index = -1; 
    while (left <= right) { 
      const middle = Math.floor(left + (right - left) / 2); 
      if(arr[middle] === target){ 
        index = middle; 
        if(direction === 'left'){ 
          right = middle - 1; 
        }else{ 
          left = middle + 1; 
        }; 
      }else if(arr[middle] < target){ 
        left = middle + 1; 
      }else{ 
        right = middle - 1; 
      }; 
    }; 
    return index; 
  }; 
  for(let i = 1; i <= 3; i++){ 
    const index = Math.floor(len * i); 
    const num = arr[index]; 
    const loIndex = search(0, index, num, 'left'); 
    const hiIndex = search(index, arr.length - 1, num, 'right'); 
    if(hiIndex - loIndex + 1 > len){ 
      return num; 
    }; 
  }; 
}; 
console.log(oneFourthElement(arr));

Đầu ra

Kết quả trong console sẽ là:

7