C++ - 二分查找完整版（包括注意細(xì)節(jié)）

發(fā)布時(shí)間：2020-08-02 19:36:15 來源：網(wǎng)絡(luò) 閱讀：1747 作者：對影欄目：編程語言

  int getPos(vector<int> A, int n, int val) 
   
         int left = 0;
	int right = n-1;
    int index = n;
 
	while(left <= right)
	{
		int mid = (left+right)/2;

		if(A[mid] == val)
        {
            if(mid < index)
			   index = mid;
            right = mid -1;
        }
		else if(A[mid] > val)
			right = mid-1;
		else if(A[mid] < val)
			left = mid+1;
	}
    
    if(index != n)
        return index;
    else
        return -1; // write code here
    }

如上述代碼所示，二分查找主要是控制左右兩個(gè)指針的遞進(jìn)關(guān)系。第一個(gè)注意事項(xiàng)是：while循環(huán)必須是left<=rigtht，而不是left<right，否則無法處理第一個(gè)數(shù)字即為要查找數(shù)字這種情況。其次，在找到的時(shí)候，還要再判斷一下是否前面有相同的關(guān)鍵字，以確保要查找的數(shù)字即為第一次出現(xiàn)的數(shù)字。

向AI問一下細(xì)節(jié)

C++ - 二分查找完整版（包括注意細(xì)節(jié)）

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽