[数据结构与算法]二分查找发（对半查找法）

问题描述：
请实现有重复数字的升序数组的二分查找
给定一个?元素有序的（升序）长度为n的整型数组?nums?和一个目标值?target??，写一个函数搜索?nums?中的第一个出现的target，如果目标值存在返回下标，否则返回?-1。

什么是二分查找法：

它的基本思想是：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取nums[n/2]与欲查找的值target作比较，如果target==nums[n/2]则找到目标值，算法终止；如?果target<nums[n/2]，则我们只要在数组nums的左半部继续搜索target；如果target>nums[n/2]，则我们只要在数组nums的右?半部继续搜索target。

二分查找法的好处：

有一个猜数游戏（正整数）。你从1开始一个一个数的猜,如果是10以内的数最多只要9次。

这看起来也能解决问题。但如果是1千以内呢？又或者是1万以内呢？显然这种方法效率很低。

但如果我们使用二分查找法。对于1千以内的数，我们就可以先猜500然后250或者750，以此方法下去不到10次就能猜出来。这种方法效率明显高很多。

现在我们开始讲如何用对半查找法解决问题

首先

必须是一个有序数列，所以我们可以先采用冒泡排序法将数列排列成一个升序的数列。

题目给定一个无序数组nums，长度为n，目标值target.

int n;//总共有n个数字
int i,j,temp;
for(i=0;i<n-1;i++)
{
    for(j=0;j<n-i-1;j++)
    {
        if(nums[j]>nums[j+1])
        {
                temp=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=temp;
        }
    }
}

然后

我们设计一个循环开始二分查找，如果查找到目标值(target)我们则返回其下标，若nums[mid]>target,则说明target的值在mid的左边所以使max=mid-1；同理，若nums[mid]<target,则使min=mid+1;若nums[mid]==target，则返回mid的值。

        int min=0;
        int max=n-1;//最后一个数的下标
        int mid;
        
        while(min<=max)//随着查找范围的不断缩进，最后min会大于max
        {
             mid=(min+max)/2;
        if(nums[mid]==target)
        {    
            return mid;
        }else if(nums[mid]<target)
        {
            min=mid+1;
        }else 
        {
            max=mid-1;
        }
            
        }
        

通过这段代码我们就能找出目标值。但是这个做法有一个局限性，target必须包含在其中且不能找出第一个目标值的下标。如nums[1,2,2,2,3]我们应该返回1但却返回了2。

所以我们可以对代码进行如下改变

?
        int min=0;
        int max=n-1;//最后一个数的下标
        int mid;
        int d=-1;//用于解决没有查找到目标值而返回-1
        
        while(min<=max)//随着查找范围的不断缩进，最后min会大于max
        {
             mid=(min+max)/2;
        if(nums[mid]==target)
        {    
            d=mid;//保存目标值下标
            max=mid-1;  向数组左边缩小范围，查找是否还有目标值
        }else if(nums[mid]<target)
        {
            min=mid+1;
        }else 
        {
            max=mid-1;
        }
            
        }
        printf("%d", d);

    

?

通过这段代码我们就能找出target的最小下标。

整个代码可以写为

#incldue<stdio.h>
int main()
{    
    int nums[n];//假定n和nums是题目已给出的数据，无需自己输入
    int n;//总共有n个数字
    int i,j,temp;
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if(nums[j]>nums[j+1])
            {
                temp=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=temp;
            }
        }
    }
        int min=0;
        int max=n-1;//最后一个数的下标
        int mid;
        int d=-1;//用于解决没有查找到目标值而返回-1
        
        while(min<=max)//随着查找范围的不断缩进，最后min会大于max
        {
             mid=(min+max)/2;
        if(nums[mid]==target)
        {    
            d=mid;//保存目标值下标
            max=mid-1;  向数组左边缩小范围，查找是否还有目标值
        }else if(nums[mid]<target)
        {
            min=mid+1;
        }else 
        {
            max=mid-1;
        }
            
        }
        printf("%d", d);
        return 0;
}