欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[查找]二分查找

程序员文章站 2022-03-14 10:11:41
...

部分有序的旋转数组

旋转数组起始就是数组元素的循环左移或者循环右移。例如:{3,4,5,1,2}为{1,2,3,4,5}的一个旋转数组。旋转数组是在非降序数组的基础上得到的,所以数组原本应该是有序的。

有序数组到旋转数组

如果真的利用循环左移或者循环右移来实现旋转数组,那么将有大量的元素要移动,所以一个好的方法要尽量的减少数组中元素的移动。

方法:

1.对数组的前部分元素做逆序操作
2.对数组的后部分元素做逆序操作
3.对数组的所有元素整体做逆序操作

逆序操作利用两个指针,一个头指针一个尾指针,都往中间移动,一次交换逆序。

旋转数组的最小值

查找最小值可以遍历一次,时间复杂度为O(n),但是还可以更快的算法,看一下旋转数组的特性:

1.旋转数组是部分有序的
2.前面的部分>后面的部分
3.最小元素出现在两部分的边界

  根据旋转数组的部分有序的特点,可以使用折半查找。

两个指针限定要查找的范围,分别是start和end
1.如果旋转数组等于原来的数组,也就是没有任何元素循环移动,也就是start对应的元素小于end对应的元素。
	那么第一个元素就是最小元素。
2.折半查找的终止条件:如果end-start=1,那么end对应的元素就是最小元素
3.取中间元素为mid=(start+end)/2
	如果mid对应的值等于start对应的值等于end对应的值,那么将是这种情况:{1,0,1,1,1,},这时
		不能确定下表2对应的1,属于前半部分升序还是后半部分升序。折半查找失效,利用顺序查找。
	如果mid对应的值大于或者等于start对应的值,说明mid对应的值仍然在第一个升序的部分,
		那么start=mid(不能等于mid+1,因为终止条件是两者相隔1)
	如果mid对应的值小于或者等于end对应的值,那说明mid对应的值在第二个升序的部分,
		那么end=mid(不能等于mid-1,因为mid可能是最小元素)

代码实现:

int minNumberInRotateArray(vector<int> rotateArray) 
    {
        if(rotateArray.size() == 0)
            return 0;
        
        int index1 = 0;
        int index2 = rotateArray.size() - 1; 
        int indexMid = index1;
        
        //数组元素循环移动量为0
        if(rotateArray[index1] < rotateArray[index2])
            return rotateArray[index1];
        
        
        while(index1 < index2)
        {
            if(index2 - index1 == 1)
            {
                indexMid = index2;
                break;
            }//if
            
            indexMid = (index1 + index2) / 2;
            //顺序查找的条件
            if(rotateArray[index1] == rotateArray[index2] && rotateArray[index1] == rotateArray[indexMid])
            {
                return MinInOrder(rotateArray, index1, index2);
            }
            
            if(rotateArray[indexMid] >= rotateArray[index1])
            {
                index1 = indexMid;
            }
            else if(rotateArray[indexMid] <= rotateArray[index2])
            {
                index2 =  indexMid;
            }
        }//while
        
        return rotateArray[indexMid];
        
    }
    
    //顺序查找
    int MinInOrder(vector<int>& nums, int index1, int index2)
    {
        int result = nums[index1];
        for(int i = index1 + 1; i <= index2; i++)
        {
            if(result > nums[i])
            {
                result = nums[i];
            }
        }
        
        return result;
    }

十分注意这道题目的Test Case:

1.输入的数组的元素个数为0
2.数组只有一个元素
3.升序的数组(循环移动量为0)
4.有重复元素的循环数组(顺序查找)

有序数组,查找某个元素重复出现的次数  

这个题目最简单的就是暴力查找,时间复杂度为O(n),因为是有序数组,可以使用二分查找,这样的话时间复杂度就能减低为O(logn),这时可能想着在找到的这个元素向其左右扩展,然后就可以找到所有的元素。其实这时的时间复杂度又降低到了O(n),一个好的方法就是利用二分查找找到这个元素的左边界,然后找到右边界,通过两个边界就能求出元素的个数。这时就用到了两次二分查找。但是总得时间复杂度仍然是O(logn)。

下面代码只是确定左边界,代码实现:

/**
 * @param array: The integer array.
 * @param target: Target number to find.
 * @return: The first position of target. Position starts from 0. 
 */
int binarySearch(vector<int> &array, int target) 
{
	// write your code here
	int i = 0;
	int j = array.size() - 1;
	
	while(i <= j)
	{
		int mid = (i + j) / 2;
		if(array[mid] == target)
		{
			if(mid != 0 && array[mid - 1] == target)//继续向左边界查找
			{
				j = mid - 1;
			}
			else
			{
				return mid;
			}
			
		}
		else if(array[mid] > target)
		{
			j = mid - 1;
		}
		else
		{
			i = mid + 1;
		}
	}
	
	return -1;
}