给定一个只包含数字0和1的排序数组，任务是高效地找到转换点。过渡点是“0”结束而“1”开始的点。
null
例如：
Input: 0 0 0 1 1Output: 3Explanation: Index of first 1 is 3Input: 0 0 0 0 1 1 1 1Output: 4Explanation: Index of first 1 is 4
天真的方法： 遍历数组并打印第一个1的索引。
- 从阵列的起点到终点遍历阵列。
- 如果当前元素为1，则打印索引并终止程序。
以下是上述方法的实施情况：
C++
// C++ implementation to find // the transition point #include<iostream> using namespace std; // Function to find the transition point int findTransitionPoint( int arr[], int n) { //perform a linear search and // return the index of //first 1 for ( int i=0; i<n ;i++) if (arr[i]==1) return i; //if no element is 1 return -1; } // Driver code int main() { int arr[] = {0, 0, 0, 0, 1, 1}; int n = sizeof (arr) / sizeof (arr[0]); int point = findTransitionPoint(arr, n); point >= 0 ? cout << "Transition point is " << point : cout<< "There is no transition point" ; return 0; } |
JAVA
// Java implementation to find the transition point import java.util.*; class GFG { // Function to find the transition point static int findTransitionPoint( int arr[], int n) { // perform a linear search and return the index of // first 1 for ( int i = 0 ; i < n ; i++) if (arr[i] == 1 ) return i; // if no element is 1 return - 1 ; } // Driver code public static void main (String[] args) { int arr[] = { 0 , 0 , 0 , 0 , 1 , 1 }; int n = arr.length; int point = findTransitionPoint(arr, n); if (point >= 0 ) System.out.print( "Transition point is " + point); else System.out.print( "There is no transition point" ); } } // This code is contributed by shivanisinghss2110 |
Python3
# Python3 implementation to find the transition point # Function to find the transition point def findTransitionPoint(arr, n): # perform a linear search and return the index of # first 1 for i in range (n): if (arr[i] = = 1 ): return i # if no element is 1 return - 1 # Driver code arr = [ 0 , 0 , 0 , 0 , 1 , 1 ] n = len (arr) point = findTransitionPoint(arr, n) if point > = 0 : print ( "Transition point is" , point) else : print ( "There is no transition point" ) # This code is contributed by shubhamsingh10 |
C#
// C# implementation to find the transition point using System; class GFG { // Function to find the transition point static int findTransitionPoint( int []arr , int n) { // perform a linear search and return the index of // first 1 for ( int i = 0; i < n ; i++) if (arr[i] == 1) return i; // if no element is 1 return -1; } // Driver method public static void Main() { int []arr = {0, 0, 0, 0, 1, 1}; int point = findTransitionPoint(arr, arr.Length); Console.Write(point >= 0 ? "Transition point is " + point : "There is no transition point" ); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript implementation to // find the transition point // Function to find the transition point function findTransitionPoint(arr, n) { // perform a linear search and // return the index of // first 1 for (let i = 0; i < n ; i++) if (arr[i] == 1) return i; // if no element is 1 return -1; } let arr = [0, 0, 0, 0, 1, 1]; let point = findTransitionPoint(arr, arr.length); document.write(point >= 0 ? "Transition point is " + point : "There is no transition point" ); </script> |
输出
Transition point is 4
复杂性分析：
- 时间复杂性： O（n），只需要一次遍历，因此时间复杂度为O（n）
- 辅助空间： O（1），不需要额外的空间。
有效方法： 其思想是使用二进制搜索，并在数组中找到最小的索引1。当数组被排序时，可以执行二进制搜索。
- 创建两个变量， L 和 R ，初始化 l=0 和 r=n-1 还有一个变量 ans=-1 储存答案。
- 重复下面的步骤直到 l<=r ，下限小于上限。
- 检查元素是否位于中间索引处 中间=（左+右）/2 ，是不是。
- 如果元素为1，则检查中间元素左侧1个元素的最小索引，即更新 r=mid-1 更新 ans=中等 .
- 如果元素为零，则检查中间元素右侧1个元素的最小索引，即更新 l=mid+1 .
以下是上述方法的实施情况：
C++
// C++ implementation to find the transition point #include<iostream> using namespace std; // Function to find the transition point int findTransitionPoint( int arr[], int n) { // Initialise lower and upper bounnds int lb = 0, ub = n-1; // Perform Binary search while (lb <= ub) { // Find mid int mid = (lb+ub)/2; // update lower_bound if mid contains 0 if (arr[mid] == 0) lb = mid+1; // If mid contains 1 else if (arr[mid] == 1) { // Check if it is the left most 1 // Return mid, if yes if (mid == 0 || (mid > 0 && arr[mid - 1] == 0)) return mid; // Else update upper_bound ub = mid-1; } } return -1; } // Driver Code int main() { int arr[] = {0, 0, 0, 0, 1, 1}; int n = sizeof (arr) / sizeof (arr[0]); int point = findTransitionPoint(arr, n); point >= 0 ? cout<< "Transition point is " << point : cout<< "There is no transition point" ; return 0; } |
JAVA
// Java implementation to find the transition point class Test { // Method to find the transition point static int findTransitionPoint( int arr[], int n) { // Initialise lower and upper bounnds int lb = 0 , ub = n - 1 ; // Perform Binary search while (lb <= ub) { // Find mid int mid = (lb + ub) / 2 ; // update lower_bound if mid contains 0 if (arr[mid] == 0 ) lb = mid + 1 ; // If mid contains 1 else if (arr[mid] == 1 ) { // Check if it is the left most 1 // Return mid, if yes if (mid == 0 || (mid > 0 && arr[mid - 1 ] == 0 )) return mid; // Else update upper_bound ub = mid - 1 ; } } return - 1 ; } // Driver method public static void main(String args[]) { int arr[] = { 0 , 0 , 0 , 0 , 1 , 1 }; int point = findTransitionPoint(arr, arr.length); System.out.println( point >= 0 ? "Transition point is " + point : "There is no transition point" ); } } |
Python3
# python implementation to find the # transition point # Function to find the transition # point def findTransitionPoint(arr, n): # Initialise lower and upper # bounnds lb = 0 ub = n - 1 # Perform Binary search while (lb < = ub): # Find mid mid = ( int )((lb + ub) / 2 ) # update lower_bound if # mid contains 0 if (arr[mid] = = 0 ): lb = mid + 1 # If mid contains 1 elif (arr[mid] = = 1 ): # Check if it is the # left most 1 Return # mid, if yes if (mid = = 0 or (mid > 0 and arr[mid - 1 ] = = 0 )): return mid # Else update # upper_bound ub = mid - 1 return - 1 # Driver code arr = [ 0 , 0 , 0 , 0 , 1 , 1 ] n = len (arr) point = findTransitionPoint(arr, n); if (point > = 0 ): print ( "Transition point is " , point) else : print ( "There is no transition point" ) # This code is contributed by Sam007 |
C#
// C# implementation to find the transition point using System; class GFG { // Method to find the transition point static int findTransitionPoint( int []arr, int n) { // Initialise lower and upper bounnds int lb = 0, ub = n-1; // Perform Binary search while (lb <= ub) { // Find mid int mid = (lb+ub)/2; // update lower_bound if mid contains 0 if (arr[mid] == 0) lb = mid+1; // If mid contains 1 else if (arr[mid] == 1) { // Check if it is the left most 1 // Return mid, if yes if (mid == 0 || (mid > 0 && arr[mid - 1] == 0)) return mid; // Else update upper_bound ub = mid-1; } } return -1; } // Driver method public static void Main() { int []arr = {0, 0, 0, 0, 1, 1}; int point = findTransitionPoint(arr, arr.Length); Console.Write(point >= 0 ? "Transition point is " + point : "There is no transition point" ); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation to find // the transition point // Function to find the // transition point function findTransitionPoint( $arr , $n ) { // Initialise lower and // upper bounnds $lb = 0; $ub = $n -1; // Perform Binary search while ( $lb <= $ub ) { // Find mid $mid = floor (( $lb + $ub ) / 2); // update lower_bound // if mid contains 0 if ( $arr [ $mid ] == 0) $lb = $mid + 1; // If mid contains 1 else if ( $arr [ $mid ] == 1) { // Check if it is the // left most 1 // Return mid, if yes if ( $mid == 0 or ( $mid > 0 and $arr [ $mid - 1] == 0)) return $mid ; // Else update upper_bound $ub = $mid - 1; } } return -1; } // Driver Code $arr = array (0, 0, 0, 0, 1, 1); $n = sizeof( $arr ); $point = findTransitionPoint( $arr , $n ); if ( $point >= 0) echo "Transition point is " , $point ; else echo "There is no transition point" ; return 0; // This code is contributed by nitin mittal. ?> |
Javascript
<script> // Javascript implementation to find the transition point // Method to find the transition point function findTransitionPoint(arr, n) { // Initialise lower and upper bounnds let lb = 0, ub = n-1; // Perform Binary search while (lb <= ub) { // Find mid let mid = parseInt((lb+ub)/2, 10); // update lower_bound if mid contains 0 if (arr[mid] == 0) lb = mid+1; // If mid contains 1 else if (arr[mid] == 1) { // Check if it is the left most 1 // Return mid, if yes if (mid == 0 || (mid > 0 && arr[mid - 1] == 0)) return mid; // Else update upper_bound ub = mid-1; } } return -1; } let arr = [0, 0, 0, 0, 1, 1]; let point = findTransitionPoint(arr, arr.length); document.write(point >= 0 ? "Transition point is " + point : "There is no transition point" ); </script> |
输出
Transition point is 4
复杂性分析：
- 时间复杂性： O（logn）。二进制搜索的时间复杂度为O（logn）。
- 辅助空间： O（1）。不需要额外的空间。
本文由 萨希尔·查布拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
