【算法】二分搜索方法 收藏防迷路

欧清辣哨

  二分搜索法运用了分治策略。给定已经排好序的n个元素，在这个n个元素中查找一个特定的元素x。

        二分搜索法的基本思想是将n个元素分成个数大致相同的两半，取arr[n/2]与x进行比较。如果x=arr[/2]，则找到x，算法终止。如果x<arr[n/2]，则只要在数组a的左半部分继续搜索x。如果x>arr[a/2]，则只要在数组arr的右半部分继续搜索x。

java实现代码：

• 
  
      public static void main(String[] args) {
  
  
• 
  
          int[] arr = {2, 7, 12, 15, 17, 21, 33, 36, 45, 65, 77, 79, 90};
  
  
• 
  
          System.out.println(binarySearch(arr, 79));
  
  
• 
  
      }
  
  
• 
  
  
  
  
• 
  
      public static int binarySearch(int[] arr, int x) {
  
  
• 
  
  
  
  
• 
  
          int left = 0; //左边界
  
  
• 
  
          int right = arr.length - 1; //右边界
  
  
• 
  
          while (left <= right) {
  
  
• 
  
              int middle = (left + right) / 2; //取中
  
  
• 
  
              if (x == arr[middle])
  
  
• 
  
                  return middle;
  
  
• 
  
              if (x > arr[middle])
  
  
• 
  
                  left = middle + 1;
  
  
• 
  
              else
  
  
• 
  
                  right = middle - 1;
  
  
• 
  
          }
  
  
• 
  
          return -1;
  
  
• 
  
      }
  
  
  

图解一下主要运行步骤：

• 数组：arr ，红色元素79是我们要查找的元素
  

      

• 循环第一次：middle是我们的二分查找指针，这次指针指向了中间，将数组分为两半
  

      

     未找到，79比33大。接下来left边界向右&#10145;&#65039;移动至middle+1的位置，指针middle重新计算

• 循环第二次
  

      

    未找到，79比65大。接下来left边界向右&#10145;&#65039;移动至middle+1的位置，指针middle重新计算

• 循环第三次
  

     

    成功 找到目标元素。

---------------------------------------------------------------------

这是数组内查找后边大元素的例子，反之查找前边小元素也是同理，right边界向左&#11013;&#65039;移动至middle+1的位置

参考文本

学习视频资料：http://www.makeru.com.cn/live/1392_1164.html?s=143793