manbetx报道:

  二分查找算法思维:又称为 折半查找,二分查找适宜对曾经排序好的数据集合停止查找。假定有一升序的数据集合,先找出升序集合中最中间的元素,将数据集合划分为两个子集,将最中间的元素和关键字key停止比拟,假设等于key则前去;假设大年夜于关键字key,则在前一个数据集合中查找;否则在后一个子集中查找,直到找到为止;假设没找到则前去-1。

  思路:

  1、先定义两个下标 , left=0 , right=arr.length -1;

  2、因为我们也不知道要轮回若干次,定义一个while轮回,终止条件为right>left

  3、因为是二分查找,定义一个mid=left + (right - left)/2; //;防止数据过大年夜溢出

  4、定义三个if语句,假设 target==arr[mid], return mid;这是经典的二分查找,我们需求在这做改良

  4.1、改良经典二分算法,二分查找是基于有序的数组,重复的元素都在一同。我们只需求在if(target==arr[mid])外面修改便可;我们需求前去第一个出现target的下标;因为我们也不知道mid前面有几个重复的元素因此我们需求一个while(mid>=0)的轮回,mid–,然后比对arr[mid]和target,只需纷歧样就终止,前去

  5、假设 target < arr[mid] , right=mid - 1;

  6、假设target > arr[mid] , left=mid + 1;

  知道了思路,我们来编程完成一下吧