Description: given a sorted ( smallest to largest) array A of n distinct integers which can be positive, negative, or zero. You want to check whether or not there is an index i that matches the corresponding item A[i]. If exists, return the item, else, return -1.
Design the fastest algorithm that you can for solving this problem. O(n) solution is not the most efficient solution for this problem. The required solution is better than O(n).
To Search:
File list (Check if you may need any files):
itemindexmatching\ItemIndexMatching\bin\Debug\input.txt
.................\.................\...\.....\ItemIndexMatching.exe
.................\.................\...\.....\ItemIndexMatching.pdb
.................\.................\...\.....\ItemIndexMatching.vshost.exe
.................\.................\...\.....\ItemIndexMatching.vshost.exe.manifest
.................\.................\...\.....\samples.txt
.................\.................\ItemIndexMatching.csproj
.................\.................\ItemIndexMatching.csproj.user
.................\.................\obj\Debug\DesignTimeResolveAssemblyReferencesInput (Hanan Hindy's conflicted copy 2014-11-17).cache
.................\.................\...\.....\DesignTimeResolveAssemblyReferencesInput.cache
.................\.................\...\.....\ItemIndexMatching.csproj.FileListAbsolute.txt
.................\.................\...\.....\ItemIndexMatching.csprojResolveAssemblyReference.cache
.................\.................\...\.....\ItemIndexMatching.exe
.................\.................\...\.....\ItemIndexMatching.pdb
.................\.................\...\.....\ModOfPower.csproj.FileListAbsolute (Hanan Hindy's conflicted copy 2014-11-17).txt
.................\.................\...\.....\ModOfPower.csproj.FileListAbsolute.txt
.................\.................\...\.....\ModOfPower.csprojResolveAssemblyReference.cache
.................\.................\Program.cs
.................\.................\...perties\AssemblyInfo.cs
.................\ItemIndexMatching.sln
.................\ItemIndexMatching.suo
.................\ItemIndexMatching.v11.suo
.................\.................\obj\Debug\TempPE
.................\.................\bin\Debug
.................\.................\obj\Debug
.................\.................\bin
.................\.................\obj
.................\.................\Properties
.................\ItemIndexMatching
itemindexmatching