二分查找 Binary search

图解

使用已排序数组是这个算法的先前条件，该方法每次将数据对半分进行查询。

迭代法 Iterative

来造轮子！！

public int binarySearch(int array[], int target){
        int left = 0;
        int right = array.length-1;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if(array[mid] == target){
                return mid;
            }else if(target < array[mid]){
                right = mid -1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }

思路

定义head，tail，mid，根据mid大小移动head 和 tail。

sudo code

两个变量记录头和尾
while 头 <= 尾  
		定义 mid ： 
		 	1. mid = target , return mid
			2. mid >target , 尾左移
			3. Mid < target，头右移
数组查找完毕，return -1

复杂度分析

时间：
	n/2,n/4,n/6…. ---> n/2^k

	最坏情况：n/2^k = 1 
			 2^k = n
			 K = log n 

	最差复杂性： O(log n)
	平均复杂性： O(log n)

空间：
	复杂性： O(1)

递归法 Recursive

来造轮子！！

public int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return mid; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return -1; 
    } 

未完
类似方法 插值搜索 (Interpolation search)