# 在排序的二進制數組中計數 1 > 原文： [https://www.geeksforgeeks.org/count-1s-sorted-binary-array/](https://www.geeksforgeeks.org/count-1s-sorted-binary-array/) 給定二進制數組以非遞增順序排序，請計算其中的 1 的數量。 例子： ``` Input: arr[] = {1, 1, 0, 0, 0, 0, 0} Output: 2 Input: arr[] = {1, 1, 1, 1, 1, 1, 1} Output: 7 Input: arr[] = {0, 0, 0, 0, 0, 0, 0} Output: 0 ``` 一個簡單的解決方案是線性遍歷數組。 簡單解決方案的時間復雜度為`O(n)`。 我們可以使用 [Binary Search](http://quiz.geeksforgeeks.org/binary-search/) 查找 O（Logn）時間的計數。 這個想法是使用 Binary Search 查找 1 的最后一次出現。 一旦找到索引最后一次出現，我們將返回 index +1 作為計數。 以下是上述想法的實現。 ## C++ ```cpp // C++ program to count one's in a boolean array #include <bits/stdc++.h> using namespace std; /* Returns counts of 1's in arr[low..high].? The array is ???assumed to be sorted in non-increasing order */ int countOnes(bool arr[], int low, int high) { ??if (high >= low) ??{ ????// get the middle index ????int mid = low + (high - low)/2; ????// check if the element at middle index is last 1 ????if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1)) ??????return mid+1; ????// If element is not last 1, recur for right side ????if (arr[mid] == 1) ??????return countOnes(arr, (mid + 1), high); ????// else recur for left side ????return countOnes(arr, low, (mid -1)); ??} ??return 0; } /* Driver program to test above functions */ int main() { ???bool arr[] = {1, 1, 1, 1, 0, 0, 0}; ???int n = sizeof(arr)/sizeof(arr[0]); ???cout << "Count of 1's in given array is " << countOnes(arr, 0, n-1); ???return 0; } ``` ## Python ``` # Python program to count one's in a boolean array # Returns counts of 1's in arr[low..high].? The array is # assumed to be sorted in non-increasing order def countOnes(arr,low,high): ????if high>=low: ????????# get the middle index ????????mid = low + (high-low)/2 ????????# check if the element at middle index is last 1 ????????if ((mid == high or arr[mid+1]==0) and (arr[mid]==1)): ????????????return mid+1 ????????# If element is not last 1, recur for right side ????????if arr[mid]==1: ????????????return countOnes(arr, (mid+1), high) ????????# else recur for left side ????????return countOnes(arr, low, mid-1) ????return 0 # Driver function arr=[1, 1, 1, 1, 0, 0, 0] print "Count of 1's in given array is",countOnes(arr, 0 , len(arr)-1) # This code is contributed by __Devesh Agrawal__ ``` ## Java ```java // Java program to count 1's in a sorted array class CountOnes { ????/* Returns counts of 1's in arr[low..high].? The ???????array is assumed to be sorted in non-increasing ???????order */ ????int countOnes(int arr[], int low, int high) ????{ ??????if (high >= low) ??????{ ????????// get the middle index ????????int mid = low + (high - low)/2; ????????// check if the element at middle index is last 1 ????????if ( (mid == high || arr[mid+1] == 0) && ?????????????(arr[mid] == 1)) ??????????return mid+1; ????????// If element is not last 1, recur for right side ????????if (arr[mid] == 1) ??????????return countOnes(arr, (mid + 1), high); ????????// else recur for left side ????????return countOnes(arr, low, (mid -1)); ??????} ??????return 0; ????} ????/* Driver program to test above functions */ ????public static void main(String args[]) ????{ ???????CountOnes ob = new CountOnes(); ???????int arr[] = {1, 1, 1, 1, 0, 0, 0}; ???????int n = arr.length; ???????System.out.println("Count of 1's in given array is " + ???????????????????????????ob.countOnes(arr, 0, n-1) ); ????} } /* This code is contributed by Rajat Mishra */ ``` ## C# ```cs // C# program to count 1's in a sorted array using System; class GFG { ????/* Returns counts of 1's in arr[low..high]. ????The array is assumed to be sorted in ????non-increasing order */ ????static int countOnes(int []arr, int low, int high) ????{ ????????if (high >= low) ????????{ ????????????// get the middle index ????????????int mid = low + (high - low) / 2; ????????????// check if the element at middle? ????????????// index is last 1 ????????????if ( (mid == high || arr[mid+1] == 0) ???????????????????????????????&& (arr[mid] == 1)) ????????????return mid+1; ????????????// If element is not last 1, recur ????????????// for right side ????????????if (arr[mid] == 1) ????????????????return countOnes(arr, (mid + 1), high); ????????????// else recur for left side ????????????return countOnes(arr, low, (mid - 1)); ????????} ????????return 0; ????} ????/* Driver program to test above functions */ ????public static void Main() ????{ ????????int []arr = {1, 1, 1, 1, 0, 0, 0}; ????????int n = arr.Length; ????????Console.WriteLine("Count of 1's in given " ??????????+ "array is " + countOnes(arr, 0, n-1) ); ????} } // This code is contributed by Sam007\. ``` ## PHP ```php <?php // PHP program to count one's in a // boolean array /* Returns counts of 1's in arr[low..high]. The array is assumed to be sorted in? non-increasing order */ function countOnes( $arr, $low, $high) { ????if ($high >= $low) ????{ ????????// get the middle index ????????$mid = $low + ($high - $low)/2; ????????// check if the element at middle ????????// index is last 1 ????????if ( ($mid == $high or $arr[$mid+1] == 0)? ???????????????????????????and ($arr[$mid] == 1)) ????????????return $mid+1; ????????// If element is not last 1, recur for? ????????// right side ????????if ($arr[$mid] == 1) ????????????return countOnes($arr, ($mid + 1), ??????????????????????????????????????????$high); ????????// else recur for left side ????????return countOnes($arr, $low, ($mid -1)); ????} ????return 0; } /* Driver program to test above functions */ $arr = array(1, 1, 1, 1, 0, 0, 0); $n = count($arr); echo "Count of 1's in given array is " ,? ??????????????????????countOnes($arr, 0, $n-1); // This code is contributed by anuj_67\. ?> ``` 輸出： ``` Count of 1's in given array is 4 ``` 上述解決方案的時間復雜度為 O（Logn）