bin search

折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。

虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费 O(n lg n) 的时间。

二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。

//折半查找


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

//折半查找 非递归方法

//二分查找/折半查找 (基于有序表)

int binSearch(int *str, int target, int len)
{
    int left = 1;
    int right = len;
    int mid;
    
    while(left<=right){
        mid = (left+right)/2;
        if(target == str[mid]) return mid;
        else if(target > str[mid]) left = mid+1;
        else right = mid - 1;
    }
    return -1;
}

//折半查找 递归方法

//二分查找/折半查找 (基于有序表)

int binSearch2(int *str, int target, int len)
{
    // todo

    return 0;
}

int main(void)
{
    int len;
    int a[20] = {0};
    int i = 0;
    printf("input string length: ");
    scanf(" %d", &len);
    //设置rand函数所用的启始种子值，以期每次产生的随机数序列均不相同。

    srand(time(NULL));
    while(i++ < len){//a[0] 为哨岗

        a[i] = rand() % 100;
        printf("%d ", a[i]);
    }
    putchar('\n');
    
    return 0;
}