设置low在有序表最左边，high在最右边，mid为(low+high)/2;取中间位置，
 
当mid的值等于k，返回第mid+1个(从0开始)
 
当mid的值大于k，从mid左边开始找，令high=mid-1;
 
当mid的值小于k，从mid右边开始找，令low=mid+1;
 
 
 
struct record (int key;int others;);
 
int blsearch(struct record r[],int k)
 
{
 
int low =0,mid,high=n-1;
 
while(low<=high)
 
{
 
mid=(low+high)/2;
 
if(r[mid].key==k) return mid+1;
 
else if(r[mid].key>k) high=mid-1;
 
else low=mid+1;
 
}
 
return 0;
 
 
 
}

二分查找
 
      二分查找也称为是折半查找，属于有序查找算法。元素必须是有序的，如果是无序的则要先进行排序操作。二分查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，二分查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
 
原理：
 
       二分查找用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
 
算法详细描述：
 
选择一个可以将列表arr大致一份为二的索引i；
检查是否有arr[i] == target；
如果不是，检查arr[i]大于还是小于target；
根据上一步的结果，确定在arr的左半部分还是右半部分搜索target。
代码实现：
 
## 递归版本
def binarySearch(arr, target):
    """
    假设arr是列表,其中元素按升序排列.
    如果target是arr中的元素,则返回True,否则返回False
    """

    def bSearch(arr, target, low, high):
        if high == low:
            return arr[low] == target
        mid = (low + high) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] > target:
            if low == mid:
                return False
            else:
                return bSearch(arr, target, low, mid - 1)
        else:
            return bSearch(arr, target, mid + 1, high)

    if len(arr) == 0:
        return False
    else:
        return bSearch(arr, target, 0, len(arr) - 1)

## 非递归版本
def binarySearch(arr, target):
    low = 0
    high = len(arr) - 1
    while low < high:
        mid = (low + high) // 2
        if target < arr[mid]:
            high = mid - 1
        elif target > arr[mid]:
            low = mid + 1
        else:
            return True
    return False
 
时间复杂度：
 
       假设，总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。由于n/2^k取整后>=1，即令n/2^k=1，可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)
 
 

这次更新数据结构查找的部分，先上一个查找的思维导图，有一个宏观认识
 
 
今天要分享的主题就是导图中用红框括起来的地方，二分查找的题用二叉树去解决，这个来源于最近做数据结构自考题，把这个题先写出来
 
题目：
 
对有序顺序表（7，12，15，18，27，32，46，65，83）用二分查找，若查找成功，则查找所需比较次数最多的键值是？
 
解读：
 
刚开始看到这道题时，完全懵，说了个啥玩意。仔细研究发现，题描述的意思是，在这个顺序表中找到一个其中值，经过中间值对比次数最多的值是多少
 
解题思路：
 
我们知道在书本上，应用二分查找是通过low high两个指针对应的键值找出中间值，让这个中间值与要找的值对比，直到找到位置，这就需要将整个顺序表所有数据找一遍，很麻烦，有没有简单方法，有的！是什么？
 
将二分查找用二叉排序树实现，比如将题中的顺序表写成二叉排序树的形式
 
 
而27，12，46取得便是二分查找中mid得值
 
从图中可以直观的看出，找到18，83的路径最长，即经过的比较次数最多，因此18，83就是答案
 
举一反三：
 
当将二分查找转化为二叉排序树时，就可以不用二分查找的平均查找公式（关键带log运算费事）
 
用二叉排序树的平均查找长度公式时，假设查找概率相等
 
则ASL=（1+2*2+2*3+2*4）/9=19/9
 
参考博客

 
 
Java有序表查找：折半查找、二分查找、差值查找和斐波那契查找
 
 
  
 

      【尊重
  原创，转载请注明出处
  】http://blog.csdn.net/guyuealian/article/details/51106238
 
 
 

       目前查找方法主要：顺序查找、有序查找（分为：折半查找即二分查找、差值查找和斐波那契查找方法）、线性索引查找、二叉排序树、平衡二叉树（AVL树）以及多路查找树（B树）、散列表查找（哈希表）等查找方法
 
 
 

       【1】顺序查找：是最简单的查找方法，其时间复杂度为O(n)，是通过
  构造一个线性表，采用遍历的方法，将记录与关键字一个一个的对比，若相等则查找成功，若全都不相等，则查找失败即记录不存在；
 
 
 

       【2】有序查找：顺序表的记录一般是无序，而有序表的记录是有序的；使用有序表查找方法时，前提条件是待查找的记录必须是已经排好序的。 有序查找分为：折半查找即二分查找、差值查找和斐波那契查找方法
  
       （1）
  折半查找法：又称二分查找，是
  最经典的有序表查找，它的前提是线性表中的记录必须是有序的（通常从小到大排列），线性表采用顺序存储的方式；
  其基本思路是：将关键字key与中间记录（（low+high）/2）进行比较；若相等，则查找成功；若关键字小于中间记录，则说明关键字可能在下半区；若大于，则说明关键字可能在上半区；不断重复上述过程，直到查找成功或失败；
 
 
 

         Java代码如下：
 
 
 

  
  
package javatest1;
public class JavaTest1 {
	public static void main(String[] args) {
		int[] num = { 1, 2, 3, 4, 5, 6 };//必须有序
		int index = Binary_Search(num, 5);
		System.out.print(index);
	}
	/* num：有序表（由小到大排列）
	 * key：要查找的关键字
	 * return：还回查找到关键字的下标，没有找到则还回-1
	 */
	private static int Binary_Search(int[] num, int key) {
		int low, high, mid;
		low = 0;
		high = num.length - 1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (key < num[mid])
				high = mid - 1;
			else if (key > num[mid])
				low = mid + 1;
			else// 如果等于则直接还回下标值
				return mid;
		}
		return -1;
	}
}
 
 
 

        （2）插值查找：对二分法查找进行改进，将要查找的关键字key与查找表中的最大最小值记录进行比较后，再确定查找的范围。在二分法查找中，是以中间记录作为查找分区的，即将表一分为二，分为上下两个查找分区：
 
 
 

  
 
 
 

        而插值查找采用插值公式的方法，来确定查找分区。可简单这样理解，比如有100个数其值在0~1000范围之间从小到大排序，你要查找关键字为5的位置下标，若采用二分法，则大概在500的地方往下查找，但采用插值的方法，可以通过插值计算出5这个关键字应该在靠近0的地方，因此查找时从50往下开始查找，从而提高效率：
 
 
 

  
 
 
 
 

  
 
 
 
 

        因此插值查找只需要在折半查找算法的代码中简单修改一下即可：
 
 
 

  
  
package javatest1;
public class JavaTest1 {

	public static void main(String[] args) {
		int[] num = { 1, 2, 3, 4, 5, 6 };// 必须有序
		int index = Insert_Search(num, 5);
		System.out.print(index);
	}
	/*
	 * num：有序表（由小到大排列） key：要查找的关键字 return：还回查找到关键字的下标，没有找到则还回-1
	 */
	private static int Insert_Search(int[] num, int key) {
		int low, high, mid;
		low = 0;
		high = num.length - 1;
		while (low <= high) {
			// mid = (low + high) / 2;//二分查找
			mid = low + (high - low) * (key - num[low])/ (num[high] - num[low]); // 插值查找
			if (key < num[mid])
				high = mid - 1;
			else if (key > num[mid])
				low = mid + 1;
			else
				// 如果等于则直接还回下标值
				return mid;
		}
		return -1;
	}
}