编写代码在一个整形有序数组中查找具体的某个数
 
我们如何在一个整形数组中找到某个具体的数呢？今天跟大家分享一个二分查找算法，二分查找又称折半查找。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功;否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
 具体代码：
 
int main()
{
	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };//定义一个整形有序数组
	int key = 0;//我们要查找的数
	scanf_s("%d", &key);
	int left = 0;//数组做下标
	int right = sizeof(arr) / sizeof(arr[0]) - 1;//数组右下标
	while (left <= right)//当满足时，进入循环
	{
		int mid = (left + right) / 2;//求出中间数的下标
		if (arr[mid] < key)//key>arr[mid],说明key在中间数右边
		{
			left = mid + 1;//左下标加重新得到一个子表
		}
		else if (arr[mid]>key)//与上面相反
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标是：%d", mid);//找到的话,打印出下标
			break;
		}
	}
	if (left>right)//
	
	{
		printf("没找到");
	}
	return 0;
}
 
运行结果；
 
 
 二分查找的优点是比较次数少，查找速度快，平均性能好，占用系统内存较少;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 
使用双指针法， 可以将时间负责度o(n^2)的解法优化为o(n)。
 
这个算法只需要遍历一次就可以得到对应数组的长度
 
图解 : （官方教程）
 
 
 
 
 
int[] a = new[] {1, 1, 1, 2, 3, 4};
public void OutPutArrayLength(int[] a)
{
	int q = 0;
	int p = q + 1;
	int index = 0;
	for (int i = 0; i < a.Length - 1; i++)
	{
   		q = i;
   		p = q + 1;
   		if (a[q] != a[p])
   		{
      		index++;
      		int tmp = a[p];
      		a[p] = a[index];
      		a[index] = tmp;
   		}
	}
}

return index+1;

Python寻找两个有序数组的中位数
 
 
审题：
 
找出意味着这是一个查找算法题
算法复杂度log级别，就是提示你是二分查找
二分查找实现一般为递归
 （1）递归包括递归体
 （2）终止条件
 
思路：
 
定理：
 
有序数组中有一半的元素小于等于数组的中位数，有一半的元素大于等于中位数（如果数组中元素个数是奇数，那么这里的一半并不是严格意义的1/2）
如果我们去掉其中一个数组比中位数小的k个数，再去掉另一个数组中比中位数大的k个数，得到的合并子数组的中位数和原来的中位数相同。
 eg：[1,2,3],[1,2,3] => [1,1,2,2,3,3]
 根据定理去除元素[2,3],[1,2] => [1,2,2,3]中位数没变。我用了特殊的例子解释，你可以自行换一个试一试。如果两个的数组长度不一样的时候，不能去掉各自的一半，要去掉相同的个数，下面会细说
 
解题思路：
 
假设两个数组的中位数分别是a[m1],b[m2]
 
if a[m1] == b[m2] ，那么刚好有一半的元素小于a[m1],那么a[m1]就是要找的中位数。参考上面的列子
if a[m1] < b[m2]，根据定理1可知，这个中位数只可能出现在a[n1/2 ~ n1-1]或者b[0 ~ n2/2].也就是说合并这两个数组的中位数和原来的数组合并的数组的中位数是一样的。 根据定理2可知：
 1.数组长度一样的时候，去除掉一半是合理的。
 2.数组长度不一样，这么做中位数可能发生变化。解决方案就是去除掉相同个数的元素。why？假设n1 < n2, 两个数组就去掉n1/2个元素。那就不在是上面的范围（a[n1/2 ~ n1-1]或者b[0 ~ n2/2]），而是a[n1/2 ~ n1-1]或者b[0 ~ (-n1/2+n2-1)].
 结论就是：只能删除a的n1/2(向下取整)
if a[m1] > b[m2],和上面分析类似，中位数只能出现在a的前半段或者b的后半段。也就是说a[0 ~ n1/2]和b[n1/2 ~ n2-1]的中位数和原来的中位数相同。
 
参考：LeetCode参考答案
 
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m, n = len(nums1), len(nums2)
        if m > n:
            nums1, nums2, m, n = nums2, nums1, n, m
        if n == 0:
            raise ValueError

        imin, imax, half_len = 0, m, (m + n + 1) // 2
        while imin <= imax:
            i = (imin + imax) // 2
            j = half_len - i
            if i < m and nums2[j-1] > nums1[i]:
                # i is too small, must increase it
                imin = i + 1
            elif i > 0 and nums1[i-1] > nums2[j]:
                # i is too big, must decrease it
                imax = i - 1
            else:
                # i is perfect

                if i == 0: max_of_left = nums2[j-1]
                elif j == 0: max_of_left = nums1[i-1]
                else: max_of_left = max(nums1[i-1], nums2[j-1])

                if (m + n) % 2 == 1:
                    return max_of_left

                if i == m: min_of_right = nums2[j]
                elif j == n: min_of_right = nums1[i]
                else: min_of_right = min(nums1[i], nums2[j])

                return (max_of_left + min_of_right) / 2.0

两个有序数组间相加和的Topk问题
 
题目描述
 
给定两个有序数组arr1和arr2，再给定一个整数k，返回来自arr1和arr2的两个数相加和最大的前k个，两个数必须分别来自两个数组
 
按照降序输出
 
[要求]
 
时间复杂度为$O(k\log k)$
 
输入描述：
 
第一行三个整数N, K分别表示数组arr1, arr2的大小，以及需要询问的数
 接下来一行N个整数，表示arr1内的元素
 再接下来一行N个整数，表示arr2内的元素
 
输出描述：
 
输出K个整数表示答案
 
示例1
 
输入
 
5 4
1 2 3 4 5
3 5 7 9 11
 
输出
 
16 15 14 14
 
备注：
 
$1⩽N⩽10^5$
 $0⩽ar{r}_{1_i},ar{r}_{2_i}⩽10^9$
 保证$1⩽K⩽2N$
 
 
题解：
 
一般涉及到 TopK 问题，首先应该想到使用堆2333。
 
我们可以知道 a[n-1] + b[n-1] 是整体的最大值，那么在这个最大值之后应该是哪个元素呢，应该是：
    
     
      
       
        m
       
       
        a
       
       
        x
       
       
        {
       
       
        a
       
       
        [
       
       
        n
       
       
        −
       
       
        1
       
       
        ]
       
       
        +
       
       
        b
       
       
        [
       
       
        n
       
       
        −
       
       
        2
       
       
        ]
       
       
        ,
       
       
        a
       
       
        [
       
       
        n
       
       
        −
       
       
        2
       
       
        ]
       
       
        +
       
       
        b
       
       
        [
       
       
        n
       
       
        −
       
       
        1
       
       
        ]
       
       
        }
       
      
      
       max\{a[n-1] + b[n-2], a[n-2] + b[n-1]\}
      
     
    max{a[n−1]+b[n−2],a[n−2]+b[n−1]}，它俩就是下一个可能最大值，绝不会出现比它们更大的元素。
 
我们可以使用一个大根堆，每个节点保存三个元素
    
     
      
       
        {
       
       
        s
       
       
        u
       
       
        m
       
       
        ,
       
       
        i
       
       
        d
       
       
        x
       
       
        1
       
       
        ,
       
       
        i
       
       
        d
       
       
        x
       
       
        2
       
       
        }
       
      
      
       \{sum, idx1, idx2\}
      
     
    {sum,idx1,idx2}，且 $a[idx1]+b[idx2]=sum$，两个下标用来表明该元素由两个数组中哪两个元素凑成的。
 
选择堆顶元素，其就是整体的最大值，将其删除，然后把两个可能的最大元素插入到堆中去：
 
 

      
       
        
         
          {
         
         
          a
         
         
          [
         
         
          i
         
         
          d
         
         
          x
         
         
          1
         
         
          −
         
         
          1
         
         
          ]
         
         
          +
         
         
          b
         
         
          [
         
         
          i
         
         
          d
         
         
          x
         
         
          2
         
         
          ]
         
         
          ,
         
         
          i
         
         
          d
         
         
          x
         
         
          1
         
         
          −
         
         
          1
         
         
          ,
         
         
          i
         
         
          d
         
         
          x
         
         
          2
         
         
          }
         
        
        
         \{a[idx1-1]+b[idx2], idx1-1, idx2\}
        
       
      {a[idx1−1]+b[idx2],idx1−1,idx2}
 
 

      
       
        
         
          {
         
         
          a
         
         
          [
         
         
          i
         
         
          d
         
         
          x
         
         
          1
         
         
          ]
         
         
          +
         
         
          b
         
         
          [
         
         
          i
         
         
          d
         
         
          x
         
         
          2
         
         
          −
         
         
          1
         
         
          ]
         
         
          ,
         
         
          i
         
         
          d
         
         
          x
         
         
          1
         
         
          ,
         
         
          i
         
         
          d
         
         
          x
         
         
          2
         
         
          −
         
         
          1
         
         
          }
         
        
        
         \{a[idx1] + b[idx2-1], idx1, idx2-1\}
        
       
      {a[idx1]+b[idx2−1],idx1,idx2−1}
 
 
这样进行 k 次操作后，就可以得到整体的 TopK 了。
 
注意：
 1. 需要判重，因为两个节点的下标有可能相等
 2. 测试数据出现无序的情况。。。。。。
 
代码：
 
#include <cstdio>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 100000;

typedef pair<int, int> PII;
typedef pair<int, PII> PIP;

int n, k;
int a[N], b[N];

int main(void) {
    scanf("%d%d", &n, &k);
    for ( int i = 0; i < n; ++i )
        scanf("%d", a + i);
    for ( int i = 0; i < n; ++i ) 
        scanf("%d", b + i);
    sort( a, a + n );
    sort( b, b + n );
    priority_queue<PIP> heap;
    unordered_map<int, bool> hash;
    heap.push({a[n-1]+b[n-1], {n-1,n-1}});
    hash[(n - 1) * N + n - 1] = true;
    while ( k-- ) {
        auto t = heap.top();
        heap.pop();
        printf("%d ", t.first);
        int x = t.second.first, y = t.second.second;
        int key = x * N + y - 1;
        if ( y && !hash.count(key) ) {
            heap.push({a[x] + b[y-1], {x, y-1}});
            hash[key] = true;
        }
        key = (x - 1) * N + y;
        if ( x  && !hash.count(key) ) {
            heap.push({a[x-1] + b[y], {x-1, y}});
            hash[key] = true;
        }
    }
    return 0;
}
 
贴一个正儿八经的 O(klogk) 复杂度代码：
 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N];
int b[N];

using PII = pair<int, int>;

int main(void) {
    int n, k;
    scanf("%d%d", &n, &k);
    for ( int i = 0; i < n; ++i )
        scanf("%d", a + i);
    for ( int i = 0; i < n; ++i )
        scanf("%d", b + i);
    sort(a, a + n);
    sort(b, b + n);
    
    auto cmp = [&](const PII& lhs, const PII& rhs) {
        return a[lhs.first] + b[lhs.second] <= a[rhs.first] + b[rhs.second];
    };
    
    priority_queue<PII, vector<PII>, decltype(cmp)> heap(cmp);
    
    int r = max(0, n - k);
    for ( int i = n - 1; i >= r ; --i ) {
        heap.emplace( move(PII(i, n - 1)) );
    }
    while ( k-- ) {
        auto [x, y] = heap.top();
        heap.pop();
        printf("%d ", a[x] + b[y]);
        if ( y ) heap.emplace( move(PII(x, y-1)) );
    }
    return 0;
}