实现一个 findIndex 函数 #137

Activity

1. sisterAn

   added

   网易

   美团

   on Dec 9, 2020
2. linlinyang commented on Dec 10, 2020

   

   linlinyang

   on Dec 10, 2020

   Last edited by sisterAn

   More actions

   二分查找

       function findIndex(arr, target){
           const len = arr.length;
           let left = 0;
           let right = len - 1;
   
           let ret = -1;
           while (left <= right) {
               const middle = ((right - left) >> 1) + left;
               const val = arr[middle];
               if (val >= target) {
                   if (val === target) {
                       ret = middle;
                   }
                   right = middle - 1;
               } else {
                   left = middle + 1;
               }
           }
   
           return ret;
       }
3. sisterAn commented on Dec 10, 2020

   

   sisterAn

   on Dec 10, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   腾讯&字节&leetcode34：在排序数组中查找元素的第一个和最后一个位置
4. jdkwky commented on Jan 7, 2021

   

   jdkwky

   on Jan 7, 2021

   Last edited by jdkwky

   More actions

   function findIndex(list, target){
               let start = 0, end = list.length -1;
               let index = -1;
               while(start !=end && start < end){
                   let mid = start + Math.floor((end - start ) / 2);
                   if(list[mid] > target){
                       end = mid -1;
                   }else if (list[mid] < target){
                       start = mid + 1;
                   }else{
                       index = mid;
                       end = mid -1;
                   }
               }
               return index;
            }
5. z253573760 commented on Feb 2, 2021

   

   z253573760

   on Feb 2, 2021

   Last edited by z253573760

   More actions

   const arr = [1, 2, 3, 4, 7, 7, 7, 9, 12, 23, 34, 45, 55, 67];
   
   function findIndex(arr, target, start = 0, end = arr.length - 1) {
     let index = Math.floor((start + end) / 2);
     const midd = arr[index];
     if (midd === target) {
       while (index >= 0) {
         if (arr[index] === target) {
           index -= 1;
         } else {
           return index + 1;
         }
       }
     }
     if (midd < target) {
       return findIndex(arr, target, index + 1, end);
     } else {
       return findIndex(arr, target, start, index - 1);
     }
   }
   const res = findIndex(arr, 7); //4
   console.log(res);
   
6. dlrandy commented on Jun 8, 2021

   

   dlrandy

   on Jun 8, 2021

   More actions

   function findIndex(sortedArray, seekElement) {
       let startIndex = 0, endIndex = sortedArray.length - 1;
       while (startIndex <= endIndex) {
           const middleIndex = startIndex + Math.floor((endIndex - startIndex)/2)
           if (sortedArray[middleIndex] === seekElement) {
              let leftIndex = middleIndex; 
              while(sortedArray[leftIndex] === seekElement && leftIndex >= 0){
                   leftIndex--;
              }
               return leftIndex + 1;
           }
          
   
           if (sortedArray[middleIndex] < seekElement) {
               startIndex = middleIndex + 1;
           } else {
               endIndex = middleIndex - 1;
           }
       }
   
       return -1;
   }
7. xllpiupiu commented on Oct 1, 2021

   

   xllpiupiu

   on Oct 1, 2021

   More actions

   /**
    * O(n)遍历 找到出现的第一个位置
    * 二分查找O(logn)遍历
    */
   //普通遍历
   Array.prototype.findIndex = function (val) {
       for (let i = 0; i < this.length; i++) {
           if (this[i] === val) return i;
       }
       return -1;
   }
   //找到结束位置
   Array.prototype.findEndIdx = function (val) {
       for (let i = this.length - 1; i >= 0; i--) {
           if (this[i] === val) return i;
       }
       return -1;
   }
   let arr = [1, 2, 2, 4];
   let index = arr.findIndex(2);
   console.log('index: ', index);
   let endIdx = arr.findEndIdx(2);
   
   console.log('endIdx: ', endIdx);
   
   /**
    * 2. 优化算法使得时间复杂度为O(logn)
    * 使用二分查找因为数组有序
    */
   Array.prototype.findStartIdx = function (val) {
       let left = 0;
       let right = this.length - 1;
       while(left<=right) {
           let midIdx = Math.floor(left+(right-left)/2);
           if(this[midIdx]===val&&this[midIdx-1]<val||midIdx===0){
               return midIdx;
           } else if(this[midIdx]>=val){
               //往左侧查找
               right = midIdx - 1;
           } else {
               left = midIdx + 1;
           }
       }
       return -1;
   }
   Array.prototype.findEndIdx2 = function(val) {
       let left = 0;
       let right = this.length - 1;
       while(left<=right) {
           let midIdx = Math.floor(left+(right-left)/2);
           if(this[midIdx]===val&&this[midIdx+1]>val||midIdx===this.length-1) {
               return midIdx;
           } else if(this[midIdx]<=val) {
               //往左侧查找
               left = midIdx + 1;
           } else {
               right = midIdx -1;
           }
       }
       return -1;
   }
   let startIdx = arr.findStartIdx(9);
   console.log('startIdx: ', startIdx);
   
   let findEndIdx2 = arr.findEndIdx2(4);
   console.log('findEndIdx2: ', findEndIdx2);
   
8. ZhaoWeiming9317 commented on Jul 19, 2022

   

   ZhaoWeiming9317

   on Jul 19, 2022

   More actions

   可以仿照python的bisect-left的源码来写呀

   function findIndex(arr: number[], target: number) {
       let lo = 0;
       let hi = arr.length - 1;
       while (lo < hi) {
           let mid = Math.floor((lo + hi) / 2);
           if (target > arr[mid]) {
               lo = mid + 1;
           } else {
               hi = mid;
           }
       }
       return lo;
   }