首页 > 其他 > 详细

力扣 :二分法

时间:2021-04-01 00:26:11      阅读:44      评论:0      收藏:0      [点我收藏+]

题目描述:

  目前在力扣题库中与二分法相关的题目占据了一大部分,不论怎样的题目坚实的思想才是解决问题的根本;

  今天就以整数二分为例来分析一下,通过使用二分法查找 target 在单调数组出现的位置·;

示例:

  输入:[2,3,6,8,9,12,45]   target:6

  输出:2

  输入:[4,6,12,45,78,98]   target:78

  输出:4

综合解法(javascript实现):

console.log(‘使用二分法查找元素在单调数组中的位置‘);
var integer_arr=[2,3,5,6,7,9,12,34];
var target=34;
var start_index=0,end_index=integer_arr.length-1;
var res_index;
while(start_index!=end_index){
    var mid_index=Math.floor((start_index+end_index)/2);
    if(integer_arr[mid_index]==target){
        res_index=mid_index;
        break;
    }else if(integer_arr[mid_index]>target){
        end_index=mid_index-1;
    }else if(integer_arr[mid_index]<target){
        start_index=mid_index+1;
    }
}
//情况一:由while条件不满足跳出的循环
if(start_index==end_index){
    res_index=end_index;
}
//情况二:由中间的integer[mid_index]==target引起的跳出循环
if(integer_arr[res_index]==target){
    console.log(`${target}所在位置索引:${res_index}`);
}else{
    console.log(‘不存在该元素‘);
}

 

总结:二分法关键在于两个关键位置的确定,一个是开始位置,一个是结束位置,每次只要满足大于或小于

   目标值就相对把结束位置置为上一次中间位置-1或把开始位置置为上次中间位置+1即可,把握住关键

   点解决问题就轻而易举;

   一步一个脚印!!!继续加油

 

力扣 :二分法

原文:https://www.cnblogs.com/gamecc666/p/14600699.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!