设n个不同的整数排好序后存于T[0:n-1]中. 若存在若干(>=0)个下标i，0<= i <=n-1, 使得T[i]=i. 设计一个有效算法找到这些个下标. 

数据输入: 第1行有一个正整数n, n<=1000000, 表示有n个整数（保证在int内）. 接下来一行是这n个整数.

结果输出:T[i]=i的下标；若没有则输出No .注意输出最后有个空格.

 
			
测试输入
			
期待的输出
			
时间限制
			
内存限制
			
额外进程
		
测试用例 1
			
以文本方式显示
			
2↵
				
0 1↵
			
			
以文本方式显示
			
0 1 ↵
			
			
1秒
			
64M
			
0
		
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+5; 
int n,a[N],b[N],s=0,flag=1;

void bs(int l,int r)
{
	int mid=(l+r)/2;
	if(l<=r)
	{
		if(a[mid]==mid)
		{
			b[s]=mid;
			s++;
			bs(l,mid-1);
			bs(mid+1,r);
		}
		else if(a[mid]<mid)
		{
			if(flag) bs(mid+1,r);
			else bs(l,mid-1);
		}
		else if(a[mid]>mid)
		{
			if(flag) bs(l,mid-1);
			else bs(mid+1,r);
		}
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	if(a[0]>a[n-1]) flag=0;
	bs(0,n-1);
	if(s>0)
	{
		sort(b,b+s);
		for(int i=0;i<s;i++) printf("%d ",b[i]);
		printf("\n");
	}
	else printf("No \n");
} 

 

public class Util {
//求最大值
     public static int maxValue(int a,int b){
    int max=0;
    if(a>b){
    max=a;
    }else{
    max=b;
    }
    return max;
     }
     //求最小值
     public static int minValue(int a,int b){
    int min=0;
    if(a>b){
    min=b;
    }else{
    min=a;
    }
    return min;
     }
     //选择排序
     public static int[] selectSort(int[] a){
    //这个地方的min的意思是默认每次排序的那个min为下坐标 而不是都是0 所以应该放在for循环里面
//     int min=0;
    int n=a.length;
    for(int i=0;i<n-1;i++){
    int min=i;
    for(int j=i+1;j<n;j++){
    if(a[min]>=a[j]){min=j;}
    }
    if(i!=min){
    int temp=a[min];
        a[min]=a[i];
        a[i]=temp;
    }
    }
    return a;
     }
     //二分查找找出下标
     public  static int middleSort(int value,int[] a){
//     boolean boo=false;
    int mid=a.length/2;
    int min=0;
    int i=1;
    int max=a.length-1;
    while(i<a.length){
     i++;
    if(value>a[mid]){
    min=mid;
    mid=(min+max)/2;
    System.out.println("one"+i);
//     mid=(mid+max)/2; 
    }
    else if(value<a[mid]){
    max=mid;
    mid=(max+min)/2;
    System.out.println("two"+i);
//     mid=(mid+min)/2;
    }else if(value==a[mid]){
//     boo=true;
    break;
    }
    }
    System.out.println("i"+i);
    return mid;
     }
     //二分查找排好序列里面是否有那个值
     public static  boolean isValueByMiddle(int value,int []a){
    boolean boo=false;
    int min=0;
    int max=a.length-1;
    int i=1;
//     int mid=a.length/2;
    while(max-min>1){
    i++;
    int mid=(min+max)/2;
//     System.out.println("mid"+mid);
    if(value>a[mid]){
    min=mid+1;
//     mid=(min+max)/2;
//     System.out.println("one"+i);
    }
    else if(value<a[mid]){
    max=mid;
//     mid=(min+max)/2;
//     System.out.println("two"+i);
    }
    else if(value==a[mid]){
//     System.out.println("in true");
    boo=true;
    break;
    }
    }
    System.out.println("i"+i);
    return boo;
     }
}

 

查找数组下标，索引，二分
二分查找数组，数组必须是有序的
按照从小到大排序
import java.util.Arrays;
public class ErFentest {
    public static void main(String[] args) {
        //二分查找数组，，数组必须按照从小到大排序
        int index = f(4);//找14的索引
        System.out.println(index);//打印14的索引
    }
    public static int f(int args) {
        int[] a = {1,4,8,12,20,24};
        int s = 0;//开始索引
        int e = a.length - 1;//结束索引
        while (s <= e) {
            int m = (s + e) / 2;//取中间数字索引
            if (a[m] == args) {
                return m;//返回该数索引
            } else if (a[m] > args) {
                e = m - 1;
            } else {
                s = m + 1;
            }

        }
        return -1;//不在返回-1

    }
}

输入为递增数组，每个元素都是整数且唯一，值都在n-1之间

首先因为值在n-1之间想到循环排序，但这个以及是排序好了，所以用二分是O（logn）。

因为这是个递增数组而且每个元素都是整数且唯一，找出一个元素的下标和内容相同。二分查找，如果发现相等则返回，如果发现不相同，则如果下标大于值则往右找，下标小于值则往左找。