经典算法之二分查找法

问题：

    如果一个数列已排序(从小到大)，查找指定元素在其中的位置。

 

解法：

    利用数列已排序的特性，从数列的中间开始搜寻，如果这个数小于所搜寻的数，则该数左边的数

一定都小于要搜寻的对象，所以无需浪费时间在左边的数；如果搜寻的数大于所搜寻的对象，则右边的

数无需再搜寻，直接搜寻左边的数。如此类推，直到找到该元素，如果找不到则返回-1。

 

    例如从数列-4， -2， 4， 6， 9， 14， 23， 100中找14。

    1、首先从中间(0 + 7)/2=4开始:

    < -4 -2 4 6 9 14 23 100 >

    2、由于9小于23，所以搜寻右边的数列

    -4 -2 4 6 9 < 14 23 100 >

    3、由于23大于14，所以搜寻左边的数列

    -4 -2 4 6 9 < 14 > 23 100

    4、找到目标，返回位置5。

 

核心代码：

1、 迭代实现

//迭代实现 static int search(int[] numbers, int num) { int low = 0, high = numbers.length - 1; int mid; while (low < high) { mid = (low + high) / 2; if (numbers[mid] == num) //找到则返回 return mid; if (numbers[mid] > num) //大于目标，找左边 high = mid - 1; else //小于目标，找右边 low = mid + 1; } return -1; //找不到，返回-1 }

 

2、 递归实现

static int search(int[] numbers, int num, int low, int high) { //下边界大于上边界，没必要进行下去了 if(low > high) return -1; //中间值 int mid = (low + high) / 2; if (numbers[mid] == num) //找到则返回 return mid; if (numbers[mid] > num) //大于目标，找左边 return search(numbers, num, low, mid - 1); else //小于目标，找右边 return search(numbers, num, mid + 1, high); }

 

全部代码：

package com.icescut.classic.algorithm; public class BinarySearch { public static void main(String[] args) { int[] numbers = { -4, -2, 4, 6, 9, 14, 23, 100 }; // 已排序 //递归实现 int res = search(numbers, 14,0,numbers.length); System.out.println("position in " + res); //迭代实现 res = search(numbers, 14); System.out.println("position in " + res); } //递归实现 static int search(int[] numbers, int num, int low, int high) { //下边界大于上边界，没必要进行下去了 if(low > high) return -1; //中间值 int mid = (low + high) / 2; if (numbers[mid] == num) //找到则返回 return mid; if (numbers[mid] > num) //大于目标，找左边 return search(numbers, num, low, mid - 1); else //小于目标，找右边 return search(numbers, num, mid + 1, high); } //迭代实现 static int search(int[] numbers, int num) { int low = 0, high = numbers.length - 1; int mid; while (low < high) { mid = (low + high) / 2; if (numbers[mid] == num) //找到则返回 return mid; if (numbers[mid] > num) //大于目标，找左边 high = mid - 1; else //小于目标，找右边 low = mid + 1; } return -1; //找不到，返回-1 } }